Farmer John prépare un voyage pour livrer un colis à Farmer Dan. Pour préserver la paix, il donne une friandise à chaque vache rencontrée. Très économe, il veut en rencontrer le moins possible.

Sa carte compte $N$ granges ($1 \le N \le 50,000$) reliées par $M$ chemins bidirectionnels ($1 \le M \le 50,000$), chacun avec $C_{i}$ vaches ($0 \le C_{i} \le 1,000$). Un chemin relie deux granges distinctes $A_{i}$ et $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$). Plusieurs chemins peuvent relier directement la même paire. FJ est dans la grange 1 et Farmer Dan dans la grange $N$.

Considérez la carte suivante :

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

Le meilleur chemin est 1 → 2 → 4 → 5 → 6, coûtant 1 + 0 + 3 + 1 = 5 friandises.

Quel est le nombre minimal de friandises à emporter, en donnant exactement une à chaque vache distincte rencontrée ? La longueur du voyage lui est indifférente.

Entrée

• Ligne 1 : les entiers $N$ et $M$ séparés par un espace.
• Lignes $2..M+1$ : les entiers $A_{i}$, $B_{i}$ et $C_{i}$ séparés par des espaces.

Sortie

• Ligne 1 : le nombre minimal de friandises nécessaires.

Exemples

Entrée 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

Sortie 1

5

Auteur du problème : Damon Doucet, 2011