Fişierul intrare/ieşire:	tunel.in, tunel.out	Sursă	preONI 2008 Runda 1
Autor	Andrei Grigorean	Adăugată de	Andrei Grigorean •wefgef
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tunelul groazei

Miruna a reusit de curand sa mituiasca functionarii publici din Tara Minunilor si astfel a capatat dreptul de a construi mult visatul tunel al groazei in parcul de distractii. Miruna crede ca dupa ce se va deschide, tunelul va fi cea mai importanta atractie a parcului. El consta din mai multe drumuri intunecate, care se intalnesc uneori in puncte de intersectie. Se stie ca sunt N astfel de puncte de intersectie, si M drumuri intunecate care leaga 2 puncte de intersectie. Pentru fiecare drum, se cunoaste timpul necesar parcurgerii lui. Tunelul are 2 usi prin care se poate intra sau iesi afara. Acestea se afla in intersectiile numerotate cu 1 si cu N. Initial, curajosii care se vor avanta sa incerce tunelul, vor intra pe usa din intersectia 1, iar apoi aceasta usa se va inchide in urma lor. Apoi, pentru a iesi afara, trebuie sa gaseasca intersectia cu numarul N. O data ce au ajuns in intersectia N calatoria lor ia sfarsit, usa se deschide si sunt obligati sa paraseasca tunelul. Deoarece este intuneric, ei nu vad aproape nimic, iar atunci cand ajung intr-o intersectie, exista aceeasi probabilitate sa isi continue traseul pe oricare din drumurile care isi au unul din capete in intersectia respectiva. Deoarece este o fetita mica si lacoma, Miruna ar dori sa stie care este media tuturor timpilor necesari pentru a parcurge drumurile de la intersectia 1 la N. Astfel ar putea estima ce profit ar avea si cat de repede si-ar recupera banii investiti in functionarii publici.

Date de intrare

Pe prima linie a fisierului de intrare tunel.in se vor gasi 2 numere intregi N si M, avand semnificatia din enunt. Pe urmatoarele M linii se vor afla cate 3 numere A, B si C, semnificand faptul ca intre intersectiile A si B exista un drum bidirectional a carui traversare dureaza C minute.

Date de iesire

In fisierul de iesire tunel.out veti scrie un singur numar real care reprezinta timpul mediu de parcurgere a drumurilor de la intersectia 1 la N. Rezultatul se accepta cu o eroare de 0.001.

Restrictii si precizari

• 2 ≤ N ≤ 255
• N-1 ≤ M ≤ 100000
• Timpul necesar traversarii oricarui drum este mai mic decat 1000.
• Din intersectia 1 se poate ajunge in oricare alta.
• Pot exista mai multe drumuri care sa lege aceleasi intersectii.

Exemplu

Cum se trimit solutii?