Farmer John prepara uma viagem para entregar um pacote a Farmer Dan. Para manter a paz, dá um petisco a cada vaca encontrada. Muito econômico, quer encontrar o menor número possível.

O mapa tem $N$ celeiros ($1 \le N \le 50,000$), ligados por $M$ caminhos bidirecionais ($1 \le M \le 50,000$), cada um com $C_{i}$ vacas ($0 \le C_{i} \le 1,000$). Um caminho liga celeiros distintos $A_{i}$ e $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$). Dois celeiros podem ter vários caminhos diretos. FJ está no celeiro 1 e Farmer Dan no $N$.

Considere este mapa:

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

A melhor rota é 1 → 2 → 4 → 5 → 6, custando 1 + 0 + 3 + 1 = 5 petiscos.

Qual o menor número de petiscos a levar, dando exatamente um a cada vaca distinta encontrada? O comprimento da viagem não importa.

Entrada

• Linha 1: inteiros $N$ e $M$ separados por espaço.
• Linhas $2..M+1$: inteiros $A_{i}$, $B_{i}$ e $C_{i}$ separados por espaços.

Saída

• Linha 1: o menor número de petiscos necessários.

Exemplos

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

Saída 1

5

Créditos do problema: Damon Doucet, 2011