In judetul Alba sunt $n$ localitati numerotate de la $1$ la $n$. Intre aceste localitati exista o retea de drumuri cu dublu sens (bidirectionale) conceputa astfel incat intre oricare doua localitati exista {**un singur drum**} care, fie e direct, fie trece prin alte localitati. Exista $n-1$ perechi de localitati cu proprietatea ca intre localitatile ce formeaza o pereche exista un drum direct. Lungimea acestor drumuri directe este cunoscuta.

Firma TOL produce bunuri de larg consum; are o fabrica in resedinta judetului care este localitatea numerotata $1$ si $n-1$ magazine, cate unul in fiecare dintre celelalte $n-1$ localitati din judet. Pentru a transporta produsele de la fabrica la cele $n-1$ magazine, TOL are la dispozitie $p$ camioane. Deoarece produsele fabricii nu sunt voluminoase si nici nu cantăresc prea mult, capacitatea camioanelor este practic nelimitata, astfel incat orice camion ar putea aproviziona intr-o singura cursa toate magazinele din judet. O cursa a unui camion incepe obligatoriu la fabrica (adica in localitatea $1$), poate trece de mai multe ori printr-o localitate si se poate termina in oricare localitate a judetului; nu este obligatoriu ca din cursă camionul sa revină la localitatea 1.

Firma TOL produce bunuri de larg consum; are o fabrica in resedinta judetului care este localitatea numerotata $1$ si $n-1$ magazine, cate unul in fiecare dintre celelalte $n-1$ localitati din judet. Pentru a transporta produsele de la fabrica la cele $n-1$ magazine, TOL are la dispozitie $p$ camioane. Deoarece produsele fabricii nu sunt voluminoase si nici nu cantaresc prea mult, capacitatea camioanelor este practic nelimitata, astfel incat orice camion ar putea aproviziona intr-o singura cursa toate magazinele din judet. O cursa a unui camion incepe obligatoriu la fabrica (adica in localitatea $1$), poate trece de mai multe ori printr-o localitate si se poate termina in oricare localitate a judetului; nu este obligatoriu ca din cursa camionul sa revina la localitatea 1.

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

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 naţional de informatica se afla la Alba Iulia. Asa ca apeleaza la voi pentru a-i rezolva problema.

h2. Date de intrare