← 返回题目列表

AtCoder · code_festival_morning_easy_c

C. 身体平衡

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

問題文

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 因为会经过最短路线,所以无法这样移动。