Takahashi is Nervous

2 secs 1024 MB
magurofly

アナウンス


  • 5/12 00:23: 制約にミスがあったため修正しました

問題文


高橋くんは非常に神経質で、歩くことにかけても非常に気を使う質です。

高橋くんの一歩は絶対に です。 それより大きかったり小さかったりすることはありえません。

高橋くんが頂点 から歩き出したとき、頂点 にたどり着くことはできるでしょうか。


頂点 辺の単純で連結な無向グラフがあります。

番目の辺は頂点 と頂点 を双方向に接続し、長さは です。

頂点 から頂点 へのパスであって、長さが の倍数になるようなものの長さの最小値を出力してください。

もしそのようなパスが存在しなければ、 -1 を出力してください。

制約


  • 入力はすべて整数である

入力


出力


答えを 行に出力せよ。

入出力例


入力例1
3 3 4
1 2 1
2 3 2
3 1 2
出力例1
4

頂点を と移動することで距離 で到着でき、これが最小です。

入力例2
4 2 7
1 3 4
2 4 2
出力例2
-1

頂点 から頂点 へ行くことができません。

入力例3
3 2 99
1 2 2000
2 3 2000
出力例3
396000

提出


Go (1.14)