Description

Farmer John must deliver a package to Farmer Dan and is preparing to set out. To keep the peace, he gives a tasty treat to every cow he meets along the way, and since FJ is frugal, he wants to encounter as few cows as possible.

FJ has a map of $N(1 \le N \le 50000)$ barns connected by $M(1 \le M \le 50000)$ bidirectional cow paths. Each path $i$ has $c[i](0 \le c[i] \le 1000)$ cows ambling along it. A cow path connects two distinct barns $a[i]$ and $b[i]$ with $1 \le a[i] \le N$, $1 \le b[i] \le N$, and $a[i] \ne b[i]$. Two barns may be directly connected by more than one path. He is currently at barn $1$, and Farmer Dan is 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 is 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 he should bring, assuming he feeds each distinct cow he meets exactly one treat? He does not care about the length of his journey.

Input Format

• Line 1: Two space-separated integers: N and M.
• Lines 2 to M+1: Three space-separated integers: A_i, B_i, and C_i.

Output Format

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

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 

Hint

Translated by ChatGPT 5