Ktree

ktree

h2. Date de intrare

Pe prima linie a fisierului de intrare ktree.in se vor afla $3$ numere intregi $N$, $M$, si $K$ avand semnificatia din enunt. Pe urmatoarele {$N-1$} linii se vor afla cate $3$ numere $A$, $B$, $C$, semnificand faptul ca intre orasul $A$ si orasul $B$ exista un drum bidirectional pentru care costul detonarii este $C$.

Pe prima linie a fisierului de intrare ktree.in se vor afla 3 numere intregi $N$, $M$, si $K$ avand semnificatia din enunt. Pe urmatoarele {$N-1$} linii se vor afla cate 3 numere $A$, $B$, $C$, semnificand faptul ca intre orasul $A$ si orasul $B$ exista un drum bidirectional pentru care costul detonarii este $C$.

h2. Date de iesire

Fisierul ktree.out va contine un singur numar intreg reprezentand costul minim cerut sau -1 in caz ca nu exista solutie.

Fisierul ktree.out va contine un singur numar intreg reprezentand costul minim cerut.

h2. Restrictii si precizari

h2. Restrictii

* $1 < N < 75$

* $1 < N < 200$

* $1 ≤ M < N$
* $1 ≤ K < N$

* Costurile drumurilor vor fi mai mici decat $1000$.

* $M + K ≤ N$
* Costurile drumurilor vor fi mai mici decat $1000$

h2. Exemple

h2. Explicatie

In primul exemplu Miruna va detona singurul drum, care are costul $3$. In al doilea exemplu, va distruge drumurile dintre urmatoarele perechi de orase: {$(2, 7)$}, {$(3, 5)$}, {$(3, 6)$}, {$(1, 4)$}.

In primul exemplu Miruna va detona singurul drum, care are costul $3$. In al doilea exemplu, va distruge drumurile dintre urmatoarele perechi de orase: {($2$, $7$)}, ($3$, $5$), ($3$, $6$), ($1$, $4$).

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