17096번 - Tourist

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

아기 민규는 이제 1번 도시에서 출발해, 2번부터 N번 도시까지를 모두 한 번씩 방문할 예정이다. 더 구체적으로 말하자면, i번째 여행에서는 1번 도시에서 출발해, i+1번 도시까지 이동하며 도중에 방문한 도로의 사진을 찍는데, 이 때 한 도로를 지나가는 데에 걸리는 시간이 t라면, t개의 사진을 찍는다. 그 후에는, 아기 민규는 부자여서 비행기를 타고 1번 도시로 돌아가서 여행을 끝낸다. 단, 이미 한 번 사진을 찍은 도로는 다시 찍지 않는다. 이 때, 아기 민규는 기름값이 아깝기 때문에 여행은 그 도시로 가는데에 걸리는 시간이 가장 적은 경로를 통해서만 갈 수 있다.

아기 민규는 사진기가 구식이라 많은 사진을 찍으면 사진기가 고장날 까봐 두려워서, 최대한 적은 도로의 사진을 찍고 싶다. 아기 민규가 찍을 수 있는 사진의 최소 개수를 구해주자. 모든 여행이 가능함은 보장된다.

첫 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 5×10⁵)

M개의 줄에 걸쳐 u와 v, t로 도로의 정보가 주어지며, 이는 u번 도시와 v번 도시를 잇는 길이 있으며 지나는 시간이 t라는 뜻이다. (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ t ≤ 5×10⁵)

아기 민규가 찍을 수 있는 사진의 최소 개수를 출력하여라.