관광객

아기 민규는 옥토끼나라의 수도인 1번 도시에 살고 있다. 옥토끼나라는 $N$개의 도시와 $M$개의 양방향 도로로 이루어져 있다. 같은 도시 쌍을 연결하는 도로는 여러 개 존재하지 않고, 양 끝 도시가 같은 도로도 존재하지 않는다.

아기 민규는 1번 도시에서 출발해 2번부터 $N$번 도시까지를 모두 한 번씩 방문할 예정이다. $i$번째 여행에서는 1번 도시에서 출발해 $i+1$번 도시까지 이동하면서 지나는 도로의 사진을 찍는다. 어떤 도로를 지나는 데 걸리는 시간이 $t$라면 그 도로에서 $t$장의 사진을 찍는다. 도착한 뒤에는 비행기를 타고 1번 도시로 돌아가 여행을 끝낸다. 이미 사진을 찍은 도로는 다시 찍지 않는다. 기름값이 아깝기 때문에, 민규는 각 여행에서 목적지까지 걸리는 시간이 가장 적은 경로로만 이동할 수 있다.

사진기가 구식이라 많은 사진을 찍으면 고장날까 봐 걱정한 민규는 최대한 적은 수의 사진을 찍고 싶다. 민규가 찍을 수 있는 사진 개수의 최솟값을 구하자. 모든 여행이 가능함은 보장된다.

첫 줄에 $N$과 $M$이 주어진다. ($1 \le N, M \le 5 \times 10^5$)

이어서 $M$개의 줄에 도로의 정보 $u$, $v$, $t$가 주어진다. 이는 $u$번 도시와 $v$번 도시를 잇는 도로가 있고 지나는 시간이 $t$라는 뜻이다. ($1 \le u, v \le N$, $u \ne v$, $1 \le t \le 5 \times 10^5$)

민규가 찍을 수 있는 사진 개수의 최솟값을 출력한다.