这个问题的解释在这里。

问题描述

今天松鼠的任务是将树上的橡子从一棵树运送到另一棵树。
森林里总共有 $N$ 棵树，每棵树都被标有从 $1$ 到 $N$ 的整数作为它的名字。此外，有 $M$ 条可以往返于不同树之间的分支（$1 \leq i \leq M$），通过第 $i$ 条分支可以双向地穿过树 $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

解释

解释