Á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.
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 |