諸注意

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

入力例 1Copy

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

出力例 1Copy

4

通る可能性のある交差点は $1, 2, 5, 6$ です。

入力例 2Copy

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

出力例 2Copy

5

通る可能性のある交差点は $1, 2, 3, 4, 5$ です。