← 返回题目列表

AtCoder · arc061_c

E. Snuke 的地铁之旅

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

分数: 600 点

问题陈述

Snuke 的小镇有一个地铁系统,包括 N 站和 M 铁路线。车站已编号 1 通过 N。每条线路均由一家公司运营。每个公司都有一个识别号。

的 i-th ( 1 \leq i \leq M ) 线路连接车站 p_i 和 q_i 双向。没有中间站。这条线路由公司运营 c_i.

您可以在有多条线路可用的车站换乘火车。

这个地铁系统使用的票价系统有点奇怪。当乘客仅乘坐同一公司运营的线路时,票价为 1 日元(日本的货币)。每当乘客改乘与当前线路不同的公司运营的线路时,乘客需支付额外票价 1 日元。从某个公司A的线路变更为其他公司的线路的乘客,再次变更为A公司的线路时,追加票价将重新开始。

Snuke 现已就位 1 想要前往车站 N 乘坐地铁。找到所需的最低票价。

约束

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq 2×10^5
  • 1 \leq p_i \leq N (1 \leq i \leq M)
  • 1 \leq q_i \leq N (1 \leq i \leq M)
  • 1 \leq c_i \leq 10^6 (1 \leq i \leq M)
  • p_i \neq q_i (1 \leq i \leq M)

输入

输入由标准输入按以下格式给出:

N M
p_1 q_1 c_1
:
p_M q_M c_M

输出

打印所需的最低票价。如果无法到达车站 N 乘坐地铁,打印 -1 。


示例输入 1

3 3
1 2 1
2 3 1
3 1 2

示例输出 1

1

使用公司 1的台词: 1 → 2 → 3。票价是 1 日元。


示例输入 2

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

示例输出 2

2

一、使用公司 1的台词: 1 → 3 → 2 → 5 → 6。然后,使用公司 5的台词: 6 → 7 → 8。票价是 2 日元。


示例输入 3

2 0

示例输出 3

-1