配点: 500 点
这个问题的解释是单击此处。
問題文
松鼠今天的工作是将橡子从一棵树搬到另一棵树。
在松鼠居住的森林里,一共有 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