Farmer John bereitet eine Reise vor, um Farmer Dan ein Paket zu liefern. Für den Frieden gibt er jeder begegneten Kuh einen Leckerbissen. Sehr sparsam, möchte er möglichst wenigen begegnen.

Seine Karte enthält $N$ Ställe ($1 \le N \le 50,000$), verbunden durch $M$ Wege in beide Richtungen ($1 \le M \le 50,000$), jeweils mit $C_{i}$ Kühen ($0 \le C_{i} \le 1,000$). Ein Weg verbindet verschiedene Ställe $A_{i}$ und $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$). Zwischen zwei Ställen können mehrere direkte Wege liegen. FJ ist in Stall 1, Farmer Dan in Stall $N$.

Betrachte diese Karte:

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

Der beste Weg ist 1 → 2 → 4 → 5 → 6 und kostet 1 + 0 + 3 + 1 = 5 Leckerbissen.

Wie viele muss er mindestens mitnehmen, wenn jede verschiedene angetroffene Kuh genau einen bekommt? Die Reiselänge ist ihm egal.

Eingabe

• Zeile 1: durch Leerzeichen getrennte ganze Zahlen $N$ und $M$.
• Zeilen $2..M+1$: durch Leerzeichen getrennte ganze Zahlen $A_{i}$, $B_{i}$ und $C_{i}$.

Ausgabe

• Zeile 1: die minimale Anzahl benötigter Leckerbissen.

Beispiele

Eingabe 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

Ausgabe 1

5

Aufgabenautor: Damon Doucet, 2011