問題文

今日のリスの仕事は、どんぐりをある木からある木まで運ぶことです。
リスの住んでいる森には全部で 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

入力例 1

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

出力例 1

1

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

4