A - 身体バランス Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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 まで最短経路を通るので、このような移動のしかたはできない。