描述

经过一段时间的交通基础设施密集发展，鲁里塔尼亚政府决定采取坚决措施加强公民对国家道路网络的信心，并设立了冒险驾驶赔偿计划（CSAD）。那些在有坑、颠簸和其他娱乐障碍的道路上行驶的人可以获得赔偿；那些在体面的道路上行驶的人要纳税。这些补偿和税款是在每条道路的入口处以现金获得和支付的，具体取决于道路上的入口点。您在从 $A$ 到 $B$ 的道路上驾驶所得和所付可能与您在从 $B$ 到 $A$ 的同一条道路上所得和所付不同。Ruritarian 当局将费用称为作为税款支付的金额或作为进入道路时作为补偿获得的金额。正费用是一种税；负费用代表补偿。

John Doe 计划利用 CSAD 来节省修理旧车所需的钱。从 $A$ 到 $B$ 开车时，John 遵循一条他称之为最佳路径：一条有益的路径，并且路径的长度最短，从 $A$ 到 $B$ 的权重最小。在 John 看来，如果路径上的所有道路都是有益的，那么这条路就是有益的，如果一条路 $(X, Y)$ 在离开 $X$ 的道路上具有最低的入场费，那么它就是有益的。路径的权重是沿路径支付的入场费之和。路径的长度累积了路径中道路的长度。问题在于帮助 John 计算给定地图上从 $A$ 到 $B$ 的最佳路径的权重和长度。

例如，在图示的道路地图上，顶点指定城市，而边代表道路。道路 $(u, v)$ 的标签 $f_{uv}[L]f_{vu}$ 显示了从 $u$ 到 $v$ 的驾驶费用 $f_{uv}$、从 $v$ 开车到 $u$ 的费用 $f_{vu}$ 以及道路的长度 $L$。从 $0$ 到 $5$ 的路径 $(0,2,4,3,5)$ 是最佳的：它是有益的，权重为 $2$（$-1+3+0+0$），长度为 $50$（$5+10+5+30$）。路径 $(0,1,4,3,5)$ 虽然有奖励且权重为 $2$，但长度为 $51$。路径 $(0,3,5)$ 的权重为 $0$，长度为 $20$，但它没有奖励。

输入

编写一个程序，从文本文件中读取多个数据集。每个数据集对一张路线图进行编码，并以四个整数开头：地图上城镇的数字 $1 \leq n \leq 1100$、道路的数字 $0 \leq m \leq 5000$、出发城镇 $0 \leq A \leq n-1$ 和目的地城镇 $0 \leq B \leq n-1$。遵循 $m$ 个数据五元组 $(u, v, f_{uv}[L]f_{vu})$，其中 $u$ 和 $v$ 是城镇标识符（$0..n-1$ 范围内的整数），$-100 \leq f_{uv}, f_{vu} \leq 100$ 是在道路上行驶的整数费用 $(u, v)$，$1 \leq L \leq 100$ 是道路的整数长度。五元组可以按任何顺序出现。除了不包含空格的五元组外，空格可以在 input 中自由出现。输入数据以文件结尾，并且是正确的。

输出

对于每个数据集，程序根据 John 的论点，从行的开头打印出从 $A$ 到 $B$ 的最佳路径的权重和长度。如果没有从 $A$ 到 $B$ 的最佳路径，则打印文本 VOID。如果从 $A$ 到 $B$ 的最佳路径的权重没有下限，则打印文本 UNBOUND。

输入数据 1

3 3 0 2 (0,1,0[1]0) (0,2,1[1]0) (1,2,1[1]0)
3 3 0 2 (0,1,-1[1]1) (0,2,0[1]0) (1,2,0[1]1)
7 11 0 5 (0,1,-1[6]4) (0,2,-1[5]4) (0,3,0[1]0)  (1,4,3[10]1)
(2,4,3[10]1) (3,4,0[5]0)  (3,5,0[30]0) (3,5,1[20]0)
 (4,6,0[3]1)  (6,5,1[8]0)  (6,6,0[2]-1)

输出数据 1

VOID
UNBOUND
2 50

提示

上表中提供了输入/输出示例。第一个数据集对一个路线图进行编码，没有从 $0$ 到 $2$ 的最佳路径。第二个数据集对应于一个映射，其最佳路径从 $0$ 到 $2$ 具有未绑定的权重。第三个数据集对上图所示的路线图进行编码。

来源

2005 年东南欧