分数: 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