AT_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$ 和 $j$，$(A_i, B_i, C_i)$ 不能相同 - $ 1 \leq C_i \leq 10^5 $ ### 示例 **输入示例 2** ```plaintext 5 5 2 1 2 1 2 3 1 2 4 2 3 4 3 4 5 2 ``` **输出示例 2** ```plaintext 4 ``` **本翻译由 AI 自动生成**

### 制約 - $ 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)