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!

Ievaddatu 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: A_i, B_i, C_i, kas atdalīti ar tukšumsimboliem. C_i - elektropārvades līnijas izveidošanas izmaksas (1<=C_i<=300) no skolas A_i līdz skolai B_i (1<=A_i,B_i<=N).

Izvaddatu vienīgajā rindā jāizvada divi naturāli skaitļi S₁ un S₂, kas atdalīti ar tukšumsimbolu - divu vislētāko elektroapgādes shēmu izmaksas (S₁ <= S₂). S₁ = S₂ tad un tikai tad, ja eksistē vairākas drošas elektroapgādes shēmas, kuru izmaksas ir vislētākās.

Uzdevums izmantots Ukrainas XIV informātikas olimpiādē 2001.gadā.