Lai godam sagatavotos starppilsētu informātikas olimpiādei, pilsētas mērs nolēmis nodrošināt skolas ar drošu elektroapgādi.
Lai to panāktu, nepieciešams izveidot elektroapgādes līniju no alternatīva elektroenerģijas avota "SPULDZESPRIEKS" līdz vienai no skolām (nav svarīgi, tieši kurai),
kā arī ar elektropārvades līnijām savienot dažas skolas savā starpā.
Tiek uzskatīts, ka skolai ir droša elektroapgāde, ja tā ir tieši saistīta ar "SPULDZESPRIEKU", vai arī tā ir savienota ar skolu, kurai ir droša elektroapgāde.
Ir zināmas izmaksas, kādas nepieciešamas, lai izveidotu elektropārvades līniju dažu skolu starpā.
Pilsētas mērs ir nolēmis izvēlēties vienu no divām vislētākajām elektroapgādes shēmām.
Noteiktas elektroapgādes shēmas izmaksu veido atsevišķu skolu pāru savienošanas izmaksu summa.
Uzrakstiet programmu, kas nosaka divu vislētāko drošo elektroapgādes shēmu izmaksas!
Teksta faila skolas.in pirmā rinda satur naturālus skaitļus N un M, kas atdalīti ar tukšumsimbolu. N norāda skolu skaitu (3<=N<=100), bet M - iespējamo savienojumu skaitu to starpā. Katrā no nākošajām M rindām ir doti trīs skaitļi: Ai, Bi, Ci, kas atdalīti ar tukšumsimboliem. Ci - elektropārvades līnijas izveidošanas izmaksas (1<=Ci<=300) no skolas Ai līdz skolai Bi (1<=Ai,Bi<=N).
Teksta faila skolas.out vienīgajā rindā jāizvada divi naturāli skaitļi S1 un S2, kas atdalīti ar tukšumsimbolu - divu vislētāko elektroapgādes shēmu izmaksas (S1 <= S2). S1 = S2 tad un tikai tad, ja eksistē vairākas drošas elektroapgādes shēmas, kuru izmaksas ir vislētākās.
| skolas.in | skolas.out |
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 |
110 121 |