Farmer John은 Farmer Dan에게 소포를 배달할 여행을 준비한다. 평화를 유지하려고 만나는 모든 소에게 맛있는 간식을 준다. 매우 검소하므로 최대한 적은 소를 만나고 싶다.

지도에는 헛간 $N$개 ($1 \le N \le 50,000$)와 이를 연결하는 양방향 소 길 $M$개 ($1 \le M \le 50,000$)가 있다. 각 길에는 소 $C_{i}$마리 ($0 \le C_{i} \le 1,000$)가 산책한다. 길은 서로 다른 헛간 $A_{i}$, $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$)를 연결한다. 두 헛간 사이에 여러 직접 연결 길이 있을 수 있다. FJ는 헛간 1, Farmer Dan은 헛간 $N$에 있다.

다음 지도를 보자.

           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3

최적 경로는 1 → 2 → 4 → 5 → 6이며 1 + 0 + 3 + 1 = 5개의 간식이 든다.

만나는 서로 다른 소마다 정확히 하나씩 준다면 간식을 최소 몇 개 가져가야 하는가? 여행 길이는 중요하지 않다.

입력

• 1번 줄: 공백으로 구분된 두 정수 $N$, $M$.
• $2..M+1$번 줄: 공백으로 구분된 세 정수 $A_{i}$, $B_{i}$, $C_{i}$.

출력

• 1번 줄: 필요한 최소 간식 수.

예제

입력 1

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

출력 1

5

문제 출제자: Damon Doucet, 2011