← 返回题目列表

AtCoder · iroha2019_day1_i

I. 松鼠的作品

中文机器翻译题面 查看原题

配点: 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

解説

解説