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