KYOPRO 시에는 $N$ 개의 교차로(1번부터 $N$번)와 $M$ 개의 양방향 도로가 있습니다. $i$ 번째 도로는 교차로 $A_i$ 와 교차로 $B_i$ 를 연결하며 이동 시간은 $C_i$ 입니다.
타로 군은 교차로 $1$ 에서 교차로 $N$ 까지 최단 경로(이동 시간이 최소인 경로)로 이동하려 합니다.
교차로 $1$ 에서 $N$ 으로 가는 **어떤 최단 경로 상에라도 포함될 가능성이 있는** 교차로의 총 개수를 구하는 프로그램을 작성하십시오. (출발지 $1$ 과 목적지 $N$ 도 포함합니다.)

[제약 조건]
• $2 \le N \le 100{,}000$
• $1 \le M \le 100{,}000$
• $1 \le A_i < B_i \le N$
• $1 \le C_i \le 10^9$
• 교차로 $1$ 에서 교차로 $N$ 으로 도달 가능한 경로가 적어도 하나 존재함이 보장됩니다.
• 입력되는 모든 값은 정수입니다.

첫째 줄에 두 정수 $N, M$ 이 공백으로 구분되어 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 도로 정보 $A_i, B_i, C_i$ 가 공백으로 구분되어 주어집니다.

어떤 최단 경로 상에라도 존재할 수 있는 교차로의 총 개수를 출력하십시오.

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

4