apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

skolas Skolu elektroapgāde 1 sek.


 Uzdevums

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!

 
 Ievaddati

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

 
 Izvaddati

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.

 
 Piemērs

skolas.inskolas.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

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

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS