== include(page="template/taskheader" task_id="ktree") ==
Miruna a ajuns in Tara Minunilor. Acest taram fermecat este alcatuit din $N$ orase legate intre ele prin {$N-1$} drumuri astfel incat din orice oras se poate ajunge in oricare altul folosind reteaua de drumuri existenta. Deoarece s-a saturat sa fie tratata ca o printesa cuminte, Miruna vrea sa detoneze exact $M$ drumuri. Unele drumuri sunt construite mai bine decat altele, de aceea Miruna are nevoie de mai mult explozibil pentru a-si atinge obiectivul malefic. Pentru fiecare drum se cunoaste pretul care trebuie platit pentru a achizitiona explozibilul necesar detonarii lui. Dupa ce drumurile alese vor fi distruse, Miruna doreste totusi sa poate circurla pornind din orasul $1$ in exact $K$ orase folosind ceea ce a ramas din reteaua stradala pentru a putea jefui negustorii veniti de peste mari si tari.
Miruna a ajuns in Tara Minunilor. Acest taram fermecat este alcatuit din $N$ orase legate intre ele prin {$N-1$} drumuri astfel incat din orice oras se poate ajunge in oricare altul folosind reteaua de drumuri existenta. Deoarece s-a saturat sa fie tratata ca o printesa cuminte, Miruna vrea sa detoneze exact K drumuri. Unele drumuri sunt construite mai bine decat altele, de aceea Miruna are nevoie de mai mult explozibil pentru a-si atinge obiectivul malefic. Pentru fiecare drum se cunoaste pretul care trebuie platit pentru a achizitiona explozibilul necesar detonarii lui. Dupa ce drumurile alese vor fi distruse, Miruna doreste totusi sa poate circurla pornind din orasul $1$ in exact $M$ orase folosind ceea ce a ramas din reteaua stradala pentru a putea jefui negustorii veniti de peste mari si tari.
Ajutati-o pe fetita ajunsa in Tara Minunilor sa cheltuie cat mai putin!
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 ≤ M < N$
* $1 ≤ K < N$
* Costurile drumurilor vor fi mai mici decat $1000$.
* ceva legat de N
h2. Exemple
h2. Exemplu
table(example). |_. ktree.in |_. ktree.out |
| 2 1 1
1 2 3
| 3 |
| 10 4 3
1 2 10
1 3 21
1 4 4
2 7 2
3 5 5
3 6 12
6 8 7
6 9 6
6 10 3
| 23 |
h2. Explicatie
|_. ktree.in |_. ktree.out |
| 2 1 1
1 2 3
| 3 ( wow ce exemplu tare )
|
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)$}.
h3. Explicatie
like duuh e singura muchie :))
== include(page="template/taskfooter" task_id="ktree") ==
