← 返回题目列表

AtCoder · icpc2012autumn_h

H. 神奇的桥梁

中文机器翻译题面 查看原题

问题陈述

一位魔术师生活在一个由 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