Farmer John prepara un viaje para entregar un paquete a Farmer Dan. Para mantener la paz, da una golosina a cada vaca que encuentra. Muy ahorrador, quiere encontrar el menor número posible.

Su mapa tiene $N$ establos ($1 \le N \le 50,000$) conectados por $M$ caminos bidireccionales ($1 \le M \le 50,000$), con $C_{i}$ vacas ($0 \le C_{i} \le 1,000$) cada uno. Un camino conecta establos distintos $A_{i}$ y $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$). Puede haber varios caminos directos entre dos establos. FJ está en el 1 y Farmer Dan en el $N$.

Considera este mapa:

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

La mejor ruta es 1 → 2 → 4 → 5 → 6, que cuesta 1 + 0 + 3 + 1 = 5 golosinas.

¿Cuál es el mínimo de golosinas que debe llevar si da exactamente una a cada vaca distinta encontrada? No le importa la longitud del viaje.

Entrada

• Línea 1: enteros $N$ y $M$ separados por espacio.
• Líneas $2..M+1$: enteros $A_{i}$, $B_{i}$ y $C_{i}$ separados por espacios.

Salida

• Línea 1: el mínimo de golosinas necesarias.

Ejemplos

Entrada 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

Salida 1

5

Autor del problema: Damon Doucet, 2011