Farmer John prepara un viaggio per consegnare un pacco a Farmer Dan. Per mantenere la pace, dà un bocconcino a ogni mucca incontrata. Molto parsimonioso, vuole incontrarne il meno possibile.

La mappa ha $N$ stalle ($1 \le N \le 50,000$) collegate da $M$ sentieri bidirezionali ($1 \le M \le 50,000$), ciascuno con $C_{i}$ mucche ($0 \le C_{i} \le 1,000$). Ogni sentiero collega stalle distinte $A_{i}$ e $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$). Possono esserci più sentieri diretti tra due stalle. FJ è nella stalla 1 e Farmer Dan nella $N$.

Considerate questa mappa:

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

Il percorso migliore è 1 → 2 → 4 → 5 → 6, che costa 1 + 0 + 3 + 1 = 5 bocconcini.

Qual è il minimo da portare se ogni diversa mucca incontrata riceve esattamente un bocconcino? La lunghezza del viaggio non importa.

Input

• Riga 1: interi $N$ e $M$ separati da spazio.
• Righe $2..M+1$: interi $A_{i}$, $B_{i}$ e $C_{i}$ separati da spazi.

Output

• Riga 1: il numero minimo di bocconcini necessari.

Esempi

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

Autore del problema: Damon Doucet, 2011