Farmer John must deliver a package to Farmer Dan, and is preparing to make his journey. To keep the peace, he gives a tasty treat to every cow that he meets along his way and, of course, FJ is so frugal that he would like to encounter as few cows as possible.

FJ has plotted a map of $N$ $1 \le N \le 50,000$ barns, connected by $M$ $1 \le M \le 50,000$ bi-directional cow paths, each with $C_{i}$ $0 \le C_{i} \le 1,000$ cows ambling along it. A cow path connects two distinct barns, $A_{i}$ and $B_{i}$ $1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$. Two barns may be directly connected by more than one path. He is currently located at barn 1, and Farmer Dan is located at barn $N$.

Consider the following map:

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

The best path for Farmer John to take is to go from 1 -> 2 -> 4 -> 5 -> 6, because it will cost him 1 + 0 + 3 + 1 = 5 treats.

Given FJ's map, what is the minimal number of treats that he should bring with him, given that he will feed each distinct cow he meets exactly one treat? He does not care about the length of his journey.

Input

• Line 1: Two space-separated integers: $N$ and $M$
• Lines $2..M+1$: Three space-separated integers: $A_{i}$, $B_{i}$, and $C_{i}$

Output

• Line 1: The minimum number of treats that FJ must bring

Examples

Input 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

Output 1

5

Problem credits: Damon Doucet, 2011