アナウンス

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

問題文

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

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

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

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

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

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

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

制約

• $1 \le N, M \le 500$
• $1 \le L \le 100$
• $1 \le A_i, B_i \le N$
• $1 \le C_i \le 2\times10^3$
• 入力はすべて整数である

入力

出力

答えを $1$ 行に出力せよ。

入出力例

3 3 4
1 2 1
2 3 2
3 1 2

4

頂点を $1 \to 2 \to 1 \to 3$ と移動することで距離 $4$ で到着でき、これが最小です。

4 2 7
1 3 4
2 4 2

-1

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

3 2 99
1 2 2000
2 3 2000

396000