Se da un graf neorientat conex cu n noduri si m muchii ponderate (costuri pozitive, graf simplu). Determinati costul celui de-al doilea cel mai mic arbore partial: cel mai mic cost total al unui arbore partial diferit STRUCTURAL de arborele partial de cost minim (poate avea acelasi cost total, daca exista un al doilea arbore optim distinct).
- 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 celui de-al doilea cel mai mic arbore partial, sau -1 daca graful nu admite decat un singur arbore partial (adica m = n - 1).
- Restrictii
- 2 <= n <= 200, n-1 <= m <= 500, 1 <= c <= 10^6, graful este conex si simplu
Exemple
Exemplul 1
Intrare
4 5 1 2 1 2 3 2 3 4 3 1 4 4 1 3 10
Iesire
7
Exemplul 2
Intrare
3 2 1 2 1 2 3 1
Iesire
-1