この問題の解説はこちら。

問題文

今日のリスの仕事は、どんぐりをある木からある木まで運ぶことです。
リスの住んでいる森には全部で $N$ 本の木があり、それぞれの木には $1$ から $N$ までの整数の名前が付けられています。 また、それぞれの木を行き来できる枝が全部で \(M\) 本あり、\(i\) 本目$(1 \\leq i \\leq M)$の枝を使って 木 $A_i$ と木 $B_i$ の間を双方向に渡れます。
それぞれの枝から次の木までは大きさ $C_i$ の隙間があり、リスがジャンプしないといけません。 リスは同じ大きさの隙間はノリノリで渡りますが、どんぐりをもちながらジャンプするのは疲れるので、 前に跳んだ隙間と違う大きさの隙間をジャンプする前に休憩をすることにしました。ただし、最初のジャンプでは休憩をしません。

リスは木 $1$ にあるどんぐりを持って、休憩回数が最少となるようなルートを通って木 $N$ まで運びます。
森の精霊であるいろはちゃんは、リスが休憩する場所とゴールの木におやつの木の実を $K$ 個ずつおいてあげたいです。
いろはちゃんはいくつの木の実を用意すればいいでしょう。

制約

• $2 \\leq N \\leq 10^5$
• $0 \\leq M \\leq 10^5$
• $1 \\leq K \\leq 10^4$
• $1 \\leq A_i, B_i \\leq N$
• $A_i \\neq B_i$
• $i \\neq j$ について $(A_i, B_i, C_i) \\neq (A_j, B_j, C_j)$
• $1 \\leq C_i \\leq 10^5$

入力

以下の形式で与えられます。

$N \\ M \\ K$ $A_1 \\ B_1 \\ C_1$ $\\vdots$ $A_M \\ B_M \\ C_M$

出力

必要な木の実の数の最小値を出力してください。リスが木 $N$ にたどり着けない場合は-1と出力してください。 そうでない場合、リスは全員同じルートを通るので、$(最少の休憩回数+1) \\times K$を出力してください。

入力例 1

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

出力例 1

1

入力例 2

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

出力例 2

4

解説

解説