flood

Īn 2005, Romānia a fost sub ape. Sute de poduri s-au darmat, sute de drumuri au fost distruse.
Primul ministru a īnfiintat un consiliu pentru situatii de urgenta care analizeaza harta tarii. Pe harta sunt marcate N localitati importante. Localitatile sunt numerotate de la 1 la N. De asemenea, pe harta sunt marcate drumurile existente īntre localitati pe care se poate circula, precum si drumurile care au fost distruse. Pentru fiecare drum distrus este specificat si costul estimat pentru reconstructia drumului.
Primul ministru doreste construirea unui numar minim de drumuri, astfel īncāt īn final sa existe legatura īntre oricare dintre cele N localitati marcate pe harta. Daca exista mai multe solutii cu numar minim de drumuri, va fi preferata aceea pentru care suma costurilor pentru reconstructie este minima.

Cerinta

Determinati drumurile care trebuie reconstruite, precum si suma minima cheltuita pentru reconstructie.

Date de intrare

Fisierul de intrare flood.in contine pe prima linie un numar natural N, reprezentānd numarul de localitati.
Pe cea de a doua linie este scris un numar natural M, care reprezinta numarul de drumuri existente pe care se poate circula.
Pe fiecare dintre urmatoarele M linii sunt scrise cāte doua numere naturale X si Y, cuprinse īntre 1 si N, separate printr-un spatiu, cu semnificatia "īntre localitatile X si Y exista un drum pe care se poate circula".
Pe urmatoarea linie este scris un numar natural P, care reprezinta numarul de drumuri distruse.
Pe fiecare dintre urmatoarele P linii sunt scrise cāte trei numere naturale separate prin cāte un spatiu X, Y si C, cu semnificatia "reconstructia drumului dintre X si Y costa C RON".

Date de iesire

Fisierul de iesire flood.out va contine pe prima linie un numar natural nr, reprezentānd numarul minim de drumuri care trebuie reconstruite. Pe cea de a doua linie va fi scris un numar natural S care reprezinta suma costurilor pentru reconstructia celor nr drumuri (minima posibil). Pe fiecare dintre urmatoarele nr linii vor fi scrise cāte trei numere naturale separate prin cāte un spatiu X Y C, cu semnificatia "drumul dintre X si Y de cost C va fi reconstruit".

Restrictii si precizari

Exemplu
flood.in flood.out

6
4
1 2
1 6
3 4
3 5
3
2 5 3
1 3 5
4 5 1

1
3
2 5 3

Timp maxim de executie/test: 0.6 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com