택배 배송

농부 현서는 농부 찬홍이에게 택배를 배달해야 합니다. 지금 막 출발하려는 참입니다. 가는 길에 마주치는 모든 소에게는 맛있는 여물을 줘야만 무사히 지나갈 수 있습니다. 다만 현서는 구두쇠라서, 되도록 적은 수의 소만 만나면서 지나가고 싶습니다.

현서에게는 지도가 한 장 있습니다. 지도에는 $N$ $(1 \le N \le 50000)$ 개의 헛간과, 헛간들을 잇는 $M$ $(1 \le M \le 50000)$ 개의 양방향 길이 그려져 있습니다. $i$번째 길에는 소가 $C_i$ $(0 \le C_i \le 1000)$ 마리 있으며, 서로 다른 두 헛간 $A_i$와 $B_i$ $(1 \le A_i, B_i \le N,\ A_i \ne B_i)$를 잇습니다. 두 헛간이 여러 개의 길로 연결되어 있을 수도 있습니다. 현서는 헛간 $1$에 있고, 찬홍이는 헛간 $N$에 있습니다.

다음 지도를 참고하세요.

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

위 지도에서 현서가 택할 수 있는 가장 좋은 경로는 $1 \to 2 \to 4 \to 5 \to 6$ 이며, 이때 만나는 소의 총합은 $1 + 0 + 3 + 1 = 5$ 입니다.

현서의 지도와 각 길에서 소를 만났을 때 줘야 하는 여물의 양이 주어질 때, 헛간 $1$에서 헛간 $N$까지 가는 동안 줘야 하는 여물의 최솟값을 구하세요. 이동 거리는 고려하지 않습니다.

첫째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어집니다.

이어지는 $M$개의 줄에는 각각 세 정수 $A_i$, $B_i$, $C_i$가 주어집니다. 이는 헛간 $A_i$와 헛간 $B_i$를 잇는 길에 소가 $C_i$마리 있다는 뜻입니다.

첫째 줄에 현서가 헛간 $1$에서 헛간 $N$까지 가는 동안 줘야 하는 여물의 최솟값을 출력합니다.