Problem
Der Präsident von Berlin hat Sie um Hilfe gebeten! Es gibt n Städte in seinem Land. Es gibt bilaterale Straßen zwischen einigen Stadtpaaren. Die Touristensaison wird bald eröffnet, aber die Straßen Berlands sind für diesen Test überhaupt nicht bereit.
Der Präsident möchte einige Straßen so reparieren, dass die Gesamtkosten für die Reparatur minimal sind und von jeder Stadt in Berlin aus nur die reparierten Straßen erreicht werden können.
Finden Sie viele Straßen, die repariert werden müssen, Ihr Freund wird Ihnen helfen. Sie müssen nur die minimalen Reparaturkosten berechnen.
Es wird sichergestellt, dass es immer die nötigen Straßen gibt.
Eingabe:
Die erste Zeile enthält zwei ganze Zahlen - n und m (2 <= n <= 300000, n - 1 <= m <= 300000).
Die folgenden m-Zeilen enthalten drei Zahlen - u, v und w (1 <= u, v <= n, 0 <= w <= 109) - die Straße zwischen den Städten u und v, deren Reparaturkosten w betragen.
|
Eingabe |
Ausgabe |
|
3 3
1 2 1
1 2 3
1 3 4
|
5 |
|
2 4
1 2 0
1 2 1
1 2 2
1 2 3
|
0 |
(c) Ibrahim Ahmad, 2018