Fişierul intrare/ieşire:	rutier.in, rutier.out	Sursă	All You Can Code 2008
Autor	Mihai Ciucu	Adăugată de	Gogu Marian •gogu
Timp execuţie pe test	0.775 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	5/5

Transport Rutier

Ministrul Transportului, Braian Tasescu, a ajuns la concluzia ca are nevoie de o crestere a popularitatii sale pentru a aspira la functia de presedinte al tarii. De aceea, el vrea sa puna la punct un program prin care incearca intretinerea cat mai buna a unui sistem de transport rutier vital tarii.

Deocamdata el este interesat de cele mai importante N orase ale tarii si vrea ca sistemul de transport sa fie format din N-1 strazi astfel incat fiecare oras sa fie legat de capitala (orasul cu indicele 1) si costul total de intretinere a strazilor sa fie cat mai mic. Desi el a gasit initial sistemul optim de transport, pe viitor se mai construiesc M strazi noi intre cele N orase asa ca de multe ori e mai bine sa modifici sistemul astfel incat costul intretinerii lui sa fie minim.

Date de intrare

Prima linie a fisierului de intrare contine numarul intreg N iar pe fiecare din urmatoarele N-1 linii se vor afla informatii despre sistemul initial, pe linia i aflandu-se doua numere intregi K si C, reprezentand orasul cel mai apropiat de capitala de care este legat orasul i si respectiv costul anual de intretine a strazii care leaga cele doua orase. Daca un oras e legat direct de capitala atunci K=1.

Linia N+1 contine numarul M iar urmatoarele M linii contin 3 numere intregi X, Y, C, care reprezinta faptul ca tocmai a fost construit un drum intre orasele X si Y care are costul anual de intretinere C.

Date de iesire

In fisierul de iesire se vor scrie M linii, linia i continand un numar intreg reprezentant costul intretinerii sistemului dupa ce au mai fost construite i strazi.