Se da un graf neorientat conex cu n noduri si m muchii ponderate (costuri pozitive, graf simplu). Determinati muchiile 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 n-1 linii, fiecare cu doua numere i j (i < j), reprezentand muchiile arborelui partial de cost minim, sortate crescator dupa i, apoi dupa j.
- Restrictii
- 1 <= n <= 100000, n-1 <= m <= 100000, 1 <= c <= 10^6, graful este conex si simplu
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
1 2 2 3 2 4 4 5
Exemplul 2
Intrare
1 0
Iesire