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

• 0 < N <= 10 000
• 0 <= M, P <= 200 000
• Costurile de reconstructie sunt numere naturale nenule <= 1000
• Drumurile dintre localitati sunt bidirectionale.
• Între doua localitati pot exista mai multe drumuri de legatura.
• Costurile totale de reconstructie nu depasesc 2 000 000 000.
• Înainte de inundatii între oricare doua localitati exista legatura.
• Se acorda punctaje partiale astfel:
  - pentru determinarea corecta a numarului minim de drumuri se acorda 20% din punctajul pe test;
  - pentru determinarea corecta a numarului minim de drumuri si a costului minim se acorda 50% din punctajul pe test.
  
  

Timp maxim de executie/test: 0.6 secunde

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