== include(page="template/taskheader" task_id="alegeri") ==
Poveste şi cerinţă...
Cum anul acesta sunt alegeri prezidentiale, mai marii tarii s-au hotarat sa repare cateva autostrazi din Tara Minunilor astfel incat sa se poata ajunga din orice oras in oricare alt oras, mergand numai pe autostrazi care nu sunt stricate. Avand la dispozitie lista cu autostrazi, precum si lista cu autostrazile stricate, voi trebuie sa ii spuneti Presedintelui care e suma minima de bani pe care trebuie sa o cheltuie ca sa multumeasca pe toata lumea si sa castige alegerile, stiind ca cele $N$ orasele din Tara Minunilor sunt codificate cu numere naturale intre $1$ si $N$.
h2. Date de intrare
Fişierul de intrare $alegeri.in$ ...
Fişierul de intrare $alegeri.in$ contine pe prima linie $T$, reprezentand numarul de teste. Un test contine pe prima linie $N$ si $M$ reprezentand numarul de orase si respectiv numarul de autostrazi din Tara Minunilor. Pe urmatoarele $M$ linii sunt descrise autostrazile, sub una din urmatoarele forme:
* $0 a b$ - care semnifica ca exista o autostrada intre orasele $a$ si $b$
* $1 a b c$ - care semnifica ca intre $a$ si $b$ exista o autostrada a carui reparatie costa $c$ lei.
h2. Date de ieşire
În fişierul de ieşire $alegeri.out$ ...
În fişierul de ieşire $alegeri.out$ se vor afisa $T$ numere, reprezentand raspunsul pentru cele $T$ teste. In caz ca nu exista nicio solutie pentru un test, se va afisa $-1$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $T = 7$
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 200 000$
* Costul unui drum este un numar pozitiv si nu depaseste $5000$
* *Atentie!* Autostrazile sunt drumuri cu doua sensuri si minim doua benzi pe sens.
h2. Exemplu
table(example). |_. alegeri.in |_. alegeri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
2 1
1 1 2 10
2 2
0 1 2
1 1 2 10
| 10
0
|
h3. Explicaţie
...
In primul exemplu in Tara Minunilor exista doar doua orase, si o autostrada stricata intre ele. Deci costul de reparare este 10. in al doilea exemplu exista o autostrada functionala si o autostrada stricata intre cele doua orase. Deci Presedintele nu trebuie sa aloce niciun ban, caci oamenii au pe unde circula, si sunt fericiti.
== include(page="template/taskfooter" task_id="alegeri") ==
