Nosaukums
Skolu elektroapgāde (skolas)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
40%

Definīcija

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 raksturojums

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: 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).


Izvaddatu raksturojums

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


Piezīmes

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


Paraugdati

Stdin
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
Stdout
110 121

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.