Farmer John przygotowuje podróż z paczką do Farmer Dan. Dla zachowania spokoju daje smakołyk każdej napotkanej krowie. Jest oszczędny, więc chce spotkać ich jak najmniej.

Mapa ma $N$ obór ($1 \le N \le 50,000$) połączonych $M$ dwukierunkowymi ścieżkami ($1 \le M \le 50,000$), każda z $C_{i}$ krowami ($0 \le C_{i} \le 1,000$). Ścieżka łączy różne obory $A_{i}$ i $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$). Między dwiema mogą być liczne bezpośrednie ścieżki. FJ jest w oborze 1, Farmer Dan w $N$.

Rozważ mapę:

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

Najlepsza trasa to 1 → 2 → 4 → 5 → 6, kosztująca 1 + 0 + 3 + 1 = 5 smakołyków.

Ile minimum zabrać, dając każdej różnej napotkanej krowie dokładnie jeden? Długość podróży go nie obchodzi.

Wejście

• Wiersz 1: liczby całkowite $N$ i $M$ oddzielone spacją.
• Wiersze $2..M+1$: liczby całkowite $A_{i}$, $B_{i}$ i $C_{i}$ oddzielone spacjami.

Wyjście

• Wiersz 1: minimalna liczba potrzebnych smakołyków.

Przykład

Wejście 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

Wyjście 1

5

Autor zadania: Damon Doucet, 2011