Se da un graf neorientat conex cu n noduri si m muchii ponderate (costuri pozitive). Determinati costul total al arborelui partial de cost minim, folosind algoritmul lui Prim.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza m linii, fiecare cu trei numere x y c, reprezentand o muchie intre x si y cu costul c.
- Date de iesire
- Se afiseaza costul total al arborelui partial de cost minim.
- Restrictii
- 1 <= n <= 100000, n-1 <= m <= 100000, 1 <= c <= 10^6, graful este conex
Exemple
Exemplul 1
Intrare
5 7 1 2 2 1 3 3 2 3 1 2 4 4 3 4 5 4 5 6 3 5 7
Iesire
13
Exemplul 2
Intrare
1 0
Iesire
0