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

== include(page="template/detailed-feedback" task_id="retea") ==
 

Aurora Flash e conectata la o retea de bloc cu $N$ calculatoare si $M$ conexiuni bidirectionale. Fiecare conexiune intre doua calculatoare $x$, $y$ are un cost asociat care reprezinta timpul necesar informatiei pentru a parcurge conexiunea respectiva. Calculatorul $1$ este calculatorul Aurorei si calculatorul $N$ este serverul. Aurora s-a saturat de atata lag (nu poate juca linistita Starcraft 2) asa ca si-a cumparat $K$ acceleratoare. Un accelerator poate fi instalat pe o anumita conexiune pentru a injumatati costul acelei conexiuni. Daca pe o conexiune sunt instalate $k$ acceleratoare costul conexiunii scade de $2^k^$ ori. Aurora vrea sa instaleze cele $K$ acceleratoare pentru a minimiza timpul necesar calculatorului ei sa comunice cu serverul. Schimbul de informatii intre doua calculatoare se produce pe drumul de cost minim, ce uneste cele doua calculatoare. Costul unui drum este egal cu suma costurilor conexiunilor de pe acel drum. Ajutati-o pe Aurora Flash sa joace Starcraft 2.
h2. Date de intrare

4686