Ciclu

ciclu

==Include(page="template/taskheader" task_id="ciclu")==

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

Acarie, fericit ca a trecut examenul la algebra pleaca in oras sa sarbatoreasca. Este atat de fericit, incat nu se multumeste cu un simplu traseu intre terase, ci vrea un ciclu pentru a fi sigur ca poate continua sa petreaca cat timp doreste. Din pacate, drumurile dintre terase au costuri diferite si nu sunt bidirectionale. Acarie nu este interesat neaparat sa minimizeze costul acestui ciclu, ci doreste sa minimizeze costul mediu al ciclului (evident, vrea sa mearga cat mai putin intre terase, adica costul ciclului imparit la numarul de terase sa fie minim).
 
Ajutati-l si de aceasta data pe Acarie si va va cinsti toata ziua.

Poveste ...

h2. Cerinta

Scrieti un program care determina costul mediu minim al unui ciclu de terase.
 
h2. Date de Intrare
 
Din fisierul $ciclu.in$ se citesc $N$ (numarul de terase), $M$ (numarul de drumuri unidirectionale) si cele $M$ drumuri directe dintre terase. Acestea sunt date fiecare pe cate o linie, reprezentate de trei intregi - terasa de unde porneste drumul, terasa unde ajunge drumul (numere intre $1$ si $N$) si costul drumului (intreg strict pozitiv mai mic decat $100.000$)
 
h2. Date de Iesire
 
Sa se afiseze in fisierul ciclu.out costul mediu minim al ciclului gasit, cu o precizie de $2$ zecimale.

...

h2. Restrictii

* 2 ≤ N ≤ 1000
* 2 ≤ M ≤ 4000

...
 
h2. Date de intrare
...

Observatii

h2. Date de iesire

* Se garanteaza ca exista cel putin un ciclu
* Rezultatul se va verifica cu o precizie de $0.1$

...

h2. Exemplu

table(example). |_. ciclu.in |_. ciclu.out |
| 4 5
1 2 1
2 3 1
1 3 1
3 4 2
4 1 3
| 1.75 |

| ciclu.in | ciclu.out |
| linia1
linia2
linia3
| linia1
linia2
|

==Include(page="template/taskfooter" task_id="ciclu")==

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