问题陈述
一位魔术师生活在一个由 N 岛屿和 M 桥梁。 有些桥是魔法桥,是由魔术师创造的。 她的魔法可以同时将所有魔法桥的长度改变为相同的非负整数。
这个国家有一个著名的两人赛车游戏。 玩家 1 从岛屿开始 S_1 玩家 2 从岛屿开始 S_2。 到达岛屿的玩家 T 首先是获胜者。
由于魔术师很喜欢看这个游戏,所以她决定通过改变魔法桥的长度来让游戏变得最精彩 使得最短路径距离之间的差异 S_1 to T 和最短路径距离 S_2 to T 尽可能小。我们忽略了岛屿内部的运动。
您的工作是计算间隙可以有多小。
请注意,她在比赛开始前指定了魔法桥的长度 一次, 并且不改变长度 比赛期间.
输入
输入由多个数据集组成。输入的末尾由五个由单个空格分隔的零表示。每个数据集都遵循 这 以下格式。输入中的每个数字都是整数。
N M S_1 S_2 T a_1 b_1 w_1 a_2 b_2 w_2 ... a_M b_M w_M
(a_i, b_i) 表示桥 i 连接两个岛屿 a_i 和 b_i.
w_i 是一个非负整数或一个字母 x (为清楚起见,引用)。如果 w_i 是一个整数,表示桥 i 是正常的,其长度为 w_i。否则,表示桥接 i 很神奇。
您可以假设以下情况:
- 1\leq N \leq 1,000
- 1\leq M \leq 2,000
- 1\leq S_1, S_2, T \leq N
- S_1, S_2, T 都是不同的。
- 1\leq a_i, b_i \leq N
- a_i \neq b_i
- 适用于所有正常桥梁 i, 0 \leq w_i \leq 1,000,000,000
- 神奇桥梁的数量 \leq 100
输出
对于每个数据集,将答案打印在一行中。
示例输入
3 2 2 3 1 1 2 1 1 3 2 4 3 1 4 2 2 1 3 2 3 x 4 3 x 0 0 0 0 0
样本输入的输出
1 1