C - Predškolák

Časový limit: 5s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Úloha

Predškoláčka (to je dieťa medzi tretím a šiestym rokom života) Petra sa teší na vianoce. Dobre vie, že u každého príbuzného (rodičia, starí rodiča, súrodenci rodičov, krstní rodičia) dostane darčeky pod stromčekom. Chce teda navštíviť všetkých príbuzných, aby mohla zozbierať všetky darčeky. Jej otecko chce tieto návštevy zorganizovať v jeden deň ako okružnú jazdu - vyrazia z domu, postupne navštívia domy všetkých príbuzných a na koniec sa vrátia k sebe domov. Keďže veľa peňazí už minuli na darčeky pre Petru, tak jeho snahou je za túto jazdu zaplatiť čo najmenej. Pomôžte mu nájsť najkratšiu cestu spájajúci domy všetkých príbuzných (začína aj končí u nich doma).

Vstup

Prvý riadok vstupu obsahuje kladné celé číslo P, určujúce počet testovacích sád. Prvý riadok testovacej sady obsahuje 2 celé čísla oddelené medzerou: počet príbuzných N (1 ≤ N ≤ 10) a počet ciest M (1 ≤ M ≤ 300). Obydlia príbuzných sú pre jednoduchosť očíslované od 1 po N. Nasledujúcich M riadkov obsahuje popis jednotlivých ciest medzi dvojicami domov. Jedna cesta je popísaná troma medzerou oddelenými celými číslami: u, v, D (1 ≤ u, v ≤ N, 1 ≤ D ≤ 100000). u,v sú čísla domov (rôznych) príbuzných na danej ceste, D je jej dĺžka. Medzi domami dvoch príbuzných môže viesť viacero ciest rôznej dĺžky.

Výstup

Pre každú testovaciu sadu vypíšte jeden riadok. Ak žiadna taká trasa neexistuje, výstup by mal obsahovať text 'Petra nebude mat vsetky darceky.'. V opačnom prípade by výstup mal obsahovať jeden riadok s minimálnou celkovou dĺžkou trasy.

Príklad

Vstup:

Výstup:

16
Petra nebude mat vsetky darceky.

11 Domáce 1