AT_iroha2019_day1_i リスのお仕事

[problemUrl]: https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_i 今日のリスの仕事は、どんぐりをある木からある木まで運ぶことです。 リスの住んでいる森には全部で $ N $ 本の木があり、それぞれの木には $ 1 $ から $ N $ までの整数の名前が付けられています。 また、それぞれの木を行き来できる枝が全部で \\(M\\) 本あり、\\(i\\) 本目$ (1\ \leq\ i\ \leq\ M) $の枝を使って 木 $ A_i $ と木 $ B_i $ の間を双方向に渡れます。 それぞれの枝から次の木までは大きさ $ C_i $ の隙間があり、リスがジャンプしないといけません。 リスは同じ大きさの隙間はノリノリで渡りますが、どんぐりをもちながらジャンプするのは疲れるので、 前に跳んだ隙間と違う大きさの隙間をジャンプする前に休憩をすることにしました。ただし、最初のジャンプでは休憩をしません。 リスは木 $ 1 $ にあるどんぐりを持って、休憩回数が最少となるようなルートを通って木 $ N $ まで運びます。 森の精霊であるいろはちゃんは、**リスが休憩する場所**と**ゴールの木**におやつの木の実を $ K $ 個ずつおいてあげたいです。 いろはちゃんはいくつの木の実を用意すればいいでしょう。

以下の形式で与えられます。 > $ N\ M\ K $ $ A_1\ B_1\ C_1 $ $ \vdots $ $ A_M\ B_M\ C_M $

必要な木の実の数の最小値を出力してください。リスが木 $ N $ にたどり着けない場合は`-1`と出力してください。 **そうでない場合、リスは全員同じルートを通るので、$ (最少の休憩回数+1)\ \times\ 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 $ ### 解説 [解説](https://img.atcoder.jp/iroha2019-day1/editorial-I.pdf) ### Sample Explanation 1 \- - - - - - ### 入力例 2 ``` 5 5 2 1 2 1 2 3 1 2 4 2 3 4 3 4 5 2 ``` ### 出力例 2 ``` 4 ``` ### 解説 \[解説\](https://img.atcoder.jp/iroha2019-day1/editorial-I.pdf)