Costul unei astfel de curse este direct proportional cu distanta parcursa. Camioanele fiind cam vechi, ele nu pot efectua decat o singura cursa (indiferent de lungimea acesteia).

Programatorul firmei TOL primeste ca sarcina de serviciu elaborarea unei planificari care sa stabileasca traseele a cel mult $p$ curse prin care sa fie aprovizionate toate localitatile judetului, iar suma distantelor parcurse de camioane in aceste curse sa fie minima. El nu se prea descurca cu programarea, dar e bine informat si stie ca lotul naţional de informatica se afla la Alba Iulia. Asa ca apeleaza la voi pentru a-i rezolva problema.

Programatorul firmei TOL primeste ca sarcina de serviciu elaborarea unei planificari care sa stabileasca traseele a cel mult $p$ curse prin care sa fie aprovizionate toate localitatile judetului, iar suma distantelor parcurse de camioane in aceste curse sa fie minima. El nu se prea descurca cu programarea, dar e bine informat si stie ca lotul national de informatica se afla la Alba Iulia. Asa ca apeleaza la voi pentru a-i rezolva problema.
h2. Cerinta
 
Scrieti un program care determina o planificare a traseelor pentru cel mult p curse astfel incat prin aceste curse sa fie aprovizionate toate cele $n-1$ magazine, iar suma distantelor parcurse de camioanele plecate in aceste curse sa fie minima.

h2. Date de intrare

Fisierul de intrare $camion2.in$ ...

Fisierul de intrare $camion2.in$ contine:
− pe prima linie doua valori numerice naturale pozitive $n$ si $p$ cu semnificatia din enunt;
− pe fiecare dintre urmatoarele $n-1$ linii, $3$ valori numerice naturale pozitive $v1$, $v2$, $d$ (v1 ≠ v2) separate printr-un spatiu, cu semnificatia: intre localitatile $v1$ si $v2$ este un drum direct de lungime $d$.
 

h2. Date de iesire