Áramszünet
A BDGPROG munkacsoport informatika versenyt szervez a 150. évforduló alkalmából.
A zökkenőmentes lebonyolítás érdekében az esetleges áramszünetre is fel kell készülni, ezért biztonsági tartalékként beüzemelnek egy helyi erőművet (a neve "Jövő"), és erre is rákötik a versenyben résztvevő iskolákat.
Feltételezhetjük, hogy a "Jövő"-vel összekötött iskolák számítógépei már megbízhatóan fognak működni, ezt a működést kell minimális költséggel garantálni. Nem kell mindenkit rákötni az erőműre, elég egy olyan iskolával összekötni, ami már (közvetve vagy közvetlen) rá van kapcsolódva a tartalék erőműre.
Tudjuk, hogy mely iskolák között lehetséges az összeköttetés kiépítése, és ezekben az esetekben ismerjük a kiépítés költségét.
Elérhetetlen kép
Feladat
Írj programot, ami megadja a legolcsóbb és a második legolcsóbb összekötési hálózat árát!
Bemenet
A bemenet több tesztesetet tartalmaz. Az első sor a tesztesetek számát tartalmazza.
Minden teszteset első sora az iskolák N számát és a lehetséges összekötések M számát adja meg. (2< N < 101) Ezután M sor következik három - három számmal: az összekötött iskolák sorszámával és az összekötés költségével. Az összekötések C költsége 1 és 300 közé esik.
Kimenet
Minden kérdéshez írjuk ki a legolcsóbb és a második legolcsóbb hálózat árát! Előfordulhat, hogy két különböző legolcsóbb hálózat van, ilyenkor két egyenlő számot kell kiadni.
Példa
| aram.be | aram.ki |
| 2
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10 |
110 121
37 37 |
