== include(page="template/taskheader" task_id="weightgraph") ==

Se aproprie sarbatorile si trebuie sa cumperi cadouri! Se da un graf neorientat conex cu $N$ noduri si $M$ muchii. Tu te afli in nodul $1$ si vrei sa strangi $K$ cadouri. Definim un drum valid un drum care pleaca din nodul $1$, care contine un numar arbitrar dar finit de noduri, si care nu contine $2$ muchii consecutive identice. Costul unui astfel de drum este produsul valorilor muchiilor ce formeaza drumul. Numarul total de cadouri pe care le vei obtine este egal cu suma costurilor tuturor drumurilor valide din acest graf.

Se aproprie sarbatorile si trebuie sa cumperi cadouri! Se da un graf neorientat conex cu $N$ noduri si $M$ muchii. Tu te afli in nodul $1$ si vrei sa strangi $K$ cadouri. Definim un drum valid un drum care pleaca din nodul $1$ si nu contine $2$ muchii consecutive identice. Costul unui astfel de drum este produsul valorilor muchiilor ce formeaza drumul. Numarul total de cadouri pe care le vei obtine este egal cu suma costurilor tuturor drumurilor valide din acest graf.

Astfel, trebuie sa ii asociati fiecarei muchii un cost mai mare sau egal ca $0$ astfel incat numarul total de cadouri pe care le veti obtine sa fie exact $K$, iar dintre toate aceste posibile atriburi trebuie afisata o atribuire care are muchia de cost maxim minima posibila (trebuie minimizata muchia de cost maxim).
h2. Date de intrare