Spannbaum
Problem
Es ist erforderlich, in der verknüpften Spalte einen Baum mit minimalem Gewicht zu finden.
Eingabe
Die erste Zeile der Eingabedatei enthält zwei natürliche Zahlen n und m - die Anzahl der Scheitelpunkte und Kanten des Graphen (1≤n≤20000, 0≤m≤100000). Die folgenden m Zeilen enthalten eine Beschreibung der Kanten nacheinander pro Zeile. Die Kantennummer i wird durch die drei natürlichen Zahlen bi, ei und wi beschrieben - die Kantenendennummer und ihr Gewicht (1≤bi,ei≤n, 0≤wi≤100000).
Der Graph ist ein zusammenhängender Graph.
Ausgabe
Geben Sie eine einzige Ganzzahl aus - das Gewicht des minimalen Kernbaums.
| Eingabe |
Ausgabe |
|
4 4
1 2 1
2 3 2
3 4 5
4 1 4
|
7 |