== 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 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.
Ajutati-o pe fetita ajunsa in Tara Minunilor sa cheltuie cat mai putin!

Miruna a ajuns in Tara Minunilor. Acest taram fermecat este alcatuit din $N$ orase legate intre ele prin {$N-1$} drumuri astfel incat din oricare oras se poate ajunge in oricare altul folosind reteaua de drumuri existenta

h2. Date de intrare