{*} sa construiasca un nou tunel cu sine intre 2 statii de metrou, platind costul A
{*} sa vanda un tunel deja sapat Societatii Culturale iGorjenesti, urmand sa fie transformat in muzeu subteran; se va incasa costul aferent tunelului respectiv

*Rusuoaica nu va sapa noi tuneluri intre doua statii intre care deja exista un tunel al carui cost aferent este mai mic sau egal decat A.*

Rusuoaica nu va sapa noi tuneluri intre doua statii intre care deja exista un tunel al carui cost aferent este mai mic sau egal decat A.
De asemenea, Rusuoaica va prioritiza cumpararea tunelurilor de cost mai mic sau egal decat A.

Rusuoaica trebuie astfel sa gaseasca costul minim de proiectare al retelei, astfel ca din oricare statie sa se poata ajunge in oricare alta statie folosind doar metroul. Costul poate fi, de altfel si negativ (tunelurile vandute vor aduce profit mai mare decat ce se va cheltui pentru finalizarea proiectului).

* $1 ≤ N ≤ 100.000$ ; $1 ≤ M ≤ 400.000$
* Atat A cat si costurile tunelurilor sunt numere naturale mai mici decat 200

* Pentru 30 puncte $1 ≤ N ≤ 1.000$
* Pentru alte 20 puncte, toate costurile tunelurilor sunt 0

* Pentru $30$ puncte $1 ≤ N ≤ 1.000$
* Pentru alte $20$ puncte, toate costurile tunelurilor sunt 0

* Se poate construi un tunel cu costul A intre 2 statii chiar daca este sapat deja unul
* Un tunel cu sine construit cu costul A nu se poate vinde dupa cumparare
* Toate tunelurile sunt bidirectionale

| -16
|

h3. Explicaţie
Rusuoaica va cumpara tunelurile (2, 3, 2), (2, 5, 1), (2, 6, 4), (4, 5, 2), (7, 3, 5) va vinde restul tunelurilor si va sapa un nou tunel intre (1, 2).

== include(page="template/taskfooter" task_id="rusuoaica") ==