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

Poveste şi cerinţă...

Rusuoaica, mare arhitecta in devenire din Manchester, a primit o tema complicata pentru ea de la facultate asa ca, evident, va cere ajutorul. Vi se da un graf neconex cu N noduri si M muchii bidirectionale cu costuri (proiectul de drumuri in constructie din tinutul iGorj, sa zicem). De altfel, puteti aplica pe graful dat operatii de tip:
* 1: platiti costul unei muchie din cele M date
* 2: creati o noua muchie intre 2 noduri oarecare platind costul A
* 3: stergeti un nod oarecare platind costul B
Rusuoaica trebuie sa determine costul minim pentru ca oricare 2 dintre nodurile ramase dupa eventuala folosire a operatiei de tip 3, sa fie conectate de un drum. (cele M muchii date nu exista, trebuie achitate cu costul dat pentru a fi create)
Ajutati-o pe Rusuoaica si spuneti-i costul total minim cerut!
 

h2. Date de intrare