Se citeste un graf neorientat conex, cu n noduri si m muchii ponderate. Determinati, folosind metoda Greedy (algoritmul lui Kruskal), costul total minim al unui arbore partial de cost minim al grafului.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza m linii, fiecare cu trei numere: cele doua noduri (numerotate de la 1 la n) si costul muchiei dintre ele.
- Date de iesire
- Se afiseaza un singur numar: costul total minim al arborelui partial de cost minim.
- Restrictii
- 1 <= n <= 1000, n-1 <= m <= 10000, 1 <= cost <= 10^6, graful este conex
Exemple
Exemplul 1
Intrare
4 5 1 2 1 2 3 2 3 4 3 1 3 4 2 4 5
Iesire
6
Exemplul 2
Intrare
3 3 1 2 1 2 3 2 1 3 3
Iesire
3