← 返回题目列表

AtCoder · tessoku_book_fl

C14. 通勤路线

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

配点: 1000 点

諸注意

第一次打印时问题文本有错误。这是一个错误,应将文本中应写为“交叉点”的部分写为“城市”。我很抱歉。了解更多详情 请参阅正誤表。

問題文

KYOPRO 市有 N 交叉路口和 M 有一条真正的路。i 主路是一个十字路口 双向连接 A_i 和交叉路口 B_i ,长度 C_i 路。

太郎在路口 我想走最短路线到达 1 到交叉路口 移动到 N 。他可能经过的路口数量为 包括 1 和交叉路口 N 在内有多少?

制約

  • 2 \leq N \leq 100000
  • 1 \leq M \leq \min(100000, N(N-1)/2)
  • 1 \leq A_i < B_i \leq N
  • 1 \leq C_i \leq 10000
  • (A_1, B_1), (A_2, B_2), \cdots, (A_M, B_M) 都不同
  • 可以通过多条道路到达任意两个路口
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1 C_1
A_2 B_2 C_2
 :
A_M B_M C_M

出力

请以整数形式输出答案。


入力例 1

6 7
1 2 15
1 4 20
2 3 65
2 5 4
3 6 50
4 5 30
5 6 8

出力例 1

4

可能的交叉点是 1, 2, 5, 6 。


入力例 2

5 6
1 2 10
1 3 10
1 4 10
2 5 20
3 5 20
4 5 20

出力例 2

5

可能的交叉点是 1, 2, 3, 4, 5 。