농부 존은 농부 댄에게 꼭 소포를 보내야 한다. 그래서 그는 농부 댄까지 가는 여행을 준비하고 있다. 평화를 유지하기 위해서, 그는 가는 길에 만나는 소들마다 맛있는 사탕을 준다. 물론 농부 존은 절약 정신이 투철하기 때문에(..), 그는 가능한 한 최소한의 소를 맞닥뜨리기를 원한다.

농부 존은 지도 위에 N(1≤N≤50,000)개의 농장과, 이 농장을 연결해주는 M(1≤M≤50,000)개의 양방향 도로 (도로는 소와 농부 존 모두 지나다닐 수 있다)를 표시했다. 각 도로에는 C_i (0≤C_i≤1,000) 마리의 소가 한가로이 거닐고 있다. 하나의 양방향 도로는 A_i, B_i (1≤A_i,B_i≤N, A_i≠B_i) 두 농장을 연결한다. 두 농장은 한 개 초과의 도로로 연결될 수 있다. 농부 존은 현재 농장 1에, 농부 댄은 농장 N에 위치해 있다.

다음 지도를 보자:

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

농부 존의 지도가 주어질 때, 소들에게 줘야 할 최소한의 사탕의 개수을 구하시오. 하나의 소에게는 하나의 사탕을 줘야 한다. 그는 몇 개의 간선을 지나는지는 신경쓰지 않는다.

입력

출력

입출력 예

입력

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

출력

5

출처:usaco 2011 MAR silver
번역:tncks0121