albero di copertura
Problem
È necessario trovare uno spanning tree di peso minimo in un grafo connesso.
Input
La prima riga del file di input contiene due numeri naturali n e m - rispettivamente il numero dei vertici e degli spigoli del grafico (1≤n≤20000, 0≤m≤100000). Le m righe successive contengono la descrizione dei bordi, uno per riga. Il numero dello spigolo i è descritto da tre numeri naturali bi, ei e wi - rispettivamente i numeri delle estremità dello spigolo e il suo peso (1≤bi,ei≤n, 0≤wi≤100000).
Il grafico è connesso.
Uscita
Stampa un singolo numero intero - il peso dell'albero di copertura minimo.
| Input |
Uscita |
|
4 4
1 2 1
2 3 2
3 4 5
4 1 4
|
7 |