Parcel Delivery

Farmer Hyunseo has to deliver a parcel to Farmer Chanhong, and he is just about to set off. To pass through peacefully, he must feed tasty fodder to every cow he meets along the way. But Hyunseo is a miser, so he wants to travel while meeting as few cows as possible.

Hyunseo has a map. It shows $N$ $(1 \le N \le 50000)$ barns and $M$ $(1 \le M \le 50000)$ two-way paths that connect them. The $i$-th path has $C_i$ $(0 \le C_i \le 1000)$ cows on it and connects two distinct barns $A_i$ and $B_i$ $(1 \le A_i, B_i \le N,\ A_i \ne B_i)$. Two barns may be connected by more than one path. Hyunseo is at barn $1$, and Chanhong is at barn $N$.

Refer to the map below.

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

On this map, the best route Hyunseo can take is $1 \to 2 \to 4 \to 5 \to 6$, for which the total number of cows he meets is $1 + 0 + 3 + 1 = 5$.

Given Hyunseo's map and the amount of fodder he must give whenever he meets cows on a path, find the minimum total fodder he must give while traveling from barn $1$ to barn $N$. The travel distance is not taken into account.

The first line contains two integers $N$ and $M$, separated by a space.

Each of the next $M$ lines contains three integers $A_i$, $B_i$, and $C_i$, meaning that the path connecting barn $A_i$ and barn $B_i$ has $C_i$ cows on it.

Print the minimum total fodder Hyunseo must give while traveling from barn $1$ to barn $N$.