諸注意

初版第 1 刷の問題文にミスがありました。本来は「交差点」と書くべきところの一部が「都市」と書かれてしまっているミスです。大変申し訳ございません。詳しくは正誤表をご覧ください。

問題文

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) はすべて異なる
• どの 2 つの交差点間も、いくつかの道路を通って到達可能である
• 入力はすべて整数

入力例 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 です。