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

Poveste şi cerinţă...

Aurora face parte dintr-o retea de bloc cu $N$ calculatoare si $M$ conexiuni bidirectionale. Fiecare conexiune intre doua noduri $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 calculatoarele $1$ si $N$ se produce pe drumul din graf de cost minim. Costul unui drum este egal cu suma costurilor conexiunilor de pe acel drum. Ajutati-o pe Aurora sa joace Starcraft 2.

h2. Date de intrare

Fişierul de intrare $retea.in$ ...

Fisierul de intrare $retea.in$ va contine pe prima linie numerele $N$, $M$ si $K$ reprezentand numarul de calculatoare din retea, numarul de conexiuni intre cele $N$ calculatoare si respectiv, numarul de acceleratoare cumparate de Aurora. Urmatoarele $M$ linii vor contine fiecare cate $3$ numere naturale $x$, $y$ si $c$ reprezentand faptul ca exista o conexiune bidirectionala de cost $c$ intre calculatoarele $x$ si $y$.

h2. Date de ieşire

h2. Date de iesire

În fişierul de ieşire $retea.out$ ...

In fisierul de iesire $retea.out$ veti afisa un singur numar $C$ cu exact $4$ zecimale, reprezentand costul minim al unui drum intre calculatoarele $1$ si $N$ dupa instalarea celor $K$ acceleratoare.

h2. Restricţii

h2. Restrictii
 
* $1 ≤ N ≤ 1 000$
* $1 ≤ M ≤ 100 000$
* $1 ≤ K ≤ 10$
* Costul oricarei conexiuni nu va depasi $10^6^$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. retea.in |_. retea.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 5 2
1 2 1
2 3 9
3 5 1
1 4 5
4 5 5
| 4.2500

|

h3. Explicaţie

h3. Explicatie

...

Aurora instaleaza ambele acceleratoare pe muchia de cost 9 ceea ce produce un drum de cost $4.25$. Daca ar fi plasat cate un accelerator pe muchiile de cost $5$ drumul minim ar fi fost egal cu $5$.

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