問題文
C先生喜爱使用斜挎包。 但是,因为据说一直只把包挂在一边肩膀上会导致身体变形,他决定注意让包在两边肩膀上挂的时间相同。
C先生居住的国家中,n 有个城镇,以及连接城镇之间的 m 一条道路。 无论哪一条 2 不同的道路,都不会有 2 两个相同的城镇相连。
某天C先生从城镇 s 到城镇 t 我们需要移动到那里。 因此,我想在途中城市 u 短暂地换一下背包,使两侧肩膀背包的时间保持相同。 但是,C 先生是最强最快的,所以前往城市 s 到城镇 u、街 u 到城镇 t 的移动会走最短路径。
请找出是否存在选择这样城市 u 的方法。
入力
输入采用以下格式给出。
n m s t x_1 y_1 d_1 x_2 y_2 d_2 ... x_m y_m d_m
- 1 第行表示城市数量的整数 n (3 \leq n \leq 1{,}000) 和表示道路数的整数 m (1 \leq m \leq min(n(n-1)/2, 10^4))。
- 每个城市分别有 1 从 n 被赋予了编号。
- 2 行表示出发城市的编号整数 s (1 \leq s \leq n)以及表示目的地城市的编号整数 t (1 \leq t \leq n)。
- 继续 来自行 m 行提供了各条道路的信息。
- x_i, y_i (1 \leq x_i, y_i \leq n 和 满足 x_i \neq y_i)以及 d_i (1 \leq d_i \leq 1{,}000)是,i 由第几条道路连接的城市 x_i 和城市 y_i 之间移动需要花费 d_i 时间,这意味着。保证可以到达
- 街 s 到城镇 t 。答案的城市
出力
存在的情况下,将该城市的编号作为 u 。如果答案候选 1 行。
有多个,可以输出任意一个。此外,如果那样的城市
不存在的情况下 u ,最后换行,不包含多余字符或空行 -1 。
。前往
入力例1
3 3 1 2 1 3 3 3 2 3 1 2 1
出力例1
3
街 1 到城镇 2 时,如果经过城市 3 ,需要花费1 → 3 在 3 的时间,并且因为3 → 2 在 3 的时间,因此可以经过城市 3 ,在那里更换包即可。按照
入力例2
4 4 1 3 1 2 2 1 4 3 2 4 3 3 4 5
出力例2
-1
1 → 2 → 4 → 3 顺序移动,通过在城市 4 更换包,可以使左右负担相等,但是 C 先生在城市 1 到城镇 4 因为会经过最短路线,所以无法这样移动。