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

Poveste si cerinta...

Dupa ce a reusit sa-si indeplineasca toate indatoririle de primar, cu succes, Dubluveu este ales presedintele Romaniei. La prima intalnire cu "Serviciul Roman de Informatii":http://www.sri.ro/, este informat de un atac terorist care ar urma sa aiba loc foarte curand. Din fericire, SRI cunoaste planurile teroristilor. Astfel, raufacatorii doresc sa atace Capitala si un oras important de la Marea Neagra. Romania are $N$ orase numerotate de la $1$ la $N$, legate prin $M$ drumuri bidirectionate de diferite lungimi. O solutie propusa de catre seful SRI este ca, toate drumurile dintre obiectivele vizate, sa fie pazite de cei $S$ soldati ai armatei. Astfel, seful SRI, ar putea cere plasarea soldatilor pe un drum, oricat de aprope de unul dintre orasele ce-l marginesc, dar nu in orase (pentru a evita panica). Fiind o personalitate care gandeste situatia in profunzime, Dubluveu si-a pus urmatoarea problema: Ce se intampla daca teroristii reusesc, totusi, sa atace unul din orasele A sau B? Soldatii ar trebui mobilizati in cel mai scurt timp in acel oras. Din fericire, toti soldatii au viteza constanta de 1m/s, iar timpul necesar mobilizarii unui soldat este egal cu maximul distantelor pana la cele doua orase.
 
h2. Cerinta
 
Pentru ca planul neceista o analiza atenta, implincand multe calcule, presedinitiea v-a insarcinat pe dumneavoastra sa va ocupati cu elaborarea sa. Deci, trebuie sa gasesiti o aranjare a celor $S$ soldati, astfel incat +oricare+ drum de la $A$ la $B$ sa fie pazit, soldatii sa nu stea in oras, iar mobilizarea totala a acestora sa fie minima.

h2. Date de intrare

Fisierul de intrare $tero.in$ ...

Pe prima linie a fisierului de intrare $tero.in$ se vor afla 3 numere $N$, $M$, si $S$ cu semnificatiile din enunt. Urmeaza apoi $M$ linii cu cate trei numere intregi $i$, $j$ si $dist$, avand semnificatia ca de intre orasul $i$ si orasul $j$ exista un drum de lungime $dist$.

h2. Date de iesire

In fisierul de iesire $tero.out$ ...

In fisierul de iesire $tero.out$ se va scrie, pe o singura linie, un numar real cu 5 zecimale exacte, reprezentand mobilizarea maxima.

h2. Restrictii

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

* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ 30 000$
* $1 ≤ S ≤ M$
* $pe un drum pot fi plasati oricati soldati$
* $lungimila unui drum nu depaseste 5 000$
* $veti primi punctaj maxim pe un test doar daca diferenta dintre raspunsul oficial si raspusul dumneavoastra este ≤ 10^-4$

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

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

| 5 6 3
1 2 2
1 4 1
2 3 1
3 4 3
3 5 1
4 5 1
| 2.5

|
h3. Explicatie

...

O posibila solutie este plasarea unui soldat la jumatatea drumului dintre 4 si 5, ceilalti doi fiind plasati la jumatatea drumului de la 2 la 3.

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