Zadanie

Hypercestovanie

Počet bodov: 50, časový limit: 2000ms

Kubik3690, dávny potomok Kubíka 369, žije v ďalekej budúcnosti v systéme Alpha Centauri. Práve postúpil na celogalaktické kolo Zenitu, ktoré sa odohráva v systéme Polaris.

Polaris je však, ako to povedať, tak nejak ďaleko. Kubik3690 bude musieť použiť práve vyvinutú technológiu hypercestovania – svetelné diaľnice medzi hviezdami.

Keďže boli však len nedávno vyvinuté, jadrová fúzia, ktorá ich poháňa, nie je ešte v plnom prúde. Túto technológiu naďalej zdokonaľujú, takže čím neskôr vojde Kubik3690 svojou vesmírnou loďou na svetelnú diaľnicu, tým viac času budú mať vedci na vylepšenia, a tým väčšie zrýchlenie jeho loď dosiahne.

Presnejšie, ak sa pripojí do svetelnej diaľnice dĺžky \(d\) parsecov v čase \(t\), jej prechod mu bude trvať \(\frac{d}{t}\) minút. Niekedy sa teda oplatí si pred ďialnicou spraviť malú pauzičku.

Pomôžte Kubik3690ovi zistiť, ako najrýchlejšie vie pricestovať na celogalaktické kolo Zenitu.

Vstup a výstup

V prvom riadku vstupu sú tri čísla \(t,~n,~m\): čas v ktorom Kubik3690 bude mať zbalené pyžamo a môže začať cestovať na Zenit, počet hviezd v galaxií, počet svetelných diaľníc.

Hviezdy sú očíslované od \(0\) po \(n-1\); Alpha Centauri je hviezda \(0\), Polaris \(n-1\).

Nasleduje \(m\) riadkov v tvare \(a~b~d\), popisujúca jednosmernú sveteľnú diaľnicu od hviezdy \(a\) k hviezde \(b\) dĺžky \(d\) parsecov; \(a \neq b\).

Vypíšte jedno číslo: najmenší čas v ktorom sa Kubik3690 vie dostať do systému hviezdy Polaris, alebo ‘Nepostupuje’ ak sa naň dostať nevie.

Vypíšte dostatočne veľa desatinných miest. Váš výstup bude považovaný za správny, ak jeho absolútna alebo relatívna odchýlka neprekročí \(10^{-6}\).

Vo všetkých vstupoch platí \(0 \leq t \leq 10^9\), \(0 \leq a,b < n\), \(0 < d \leq 10^9\).

V tretine vstupov platí \(n = 2, m = 1\).

V druhej tretine vstupov platí \(2 \leq n \leq 1\,000\), \(0 \leq m \leq 1\,000\).

V tretej tretine vstupov platí \(2 \leq n \leq 2 \cdot 10^5\), \(0 \leq m \leq 5 \cdot 10^5\).

Príklady

Input:

0 2 1
1 0 47

Output:

Nepostupuje

Nie je radno cestovať svetelnou diaľnicou v protismere.

Input:

0 2 1
0 1 47

Output:

13.71130920

Príklad vstupu z prvej sady. V akom čase sa to Kubik3690ovi oplatilo vyraziť? To necháme na vás.

Input:

1 3 3
0 2 3
0 1 2
1 2 1

Output:

2.18198052

Kubíkovi sa oplatí chvíľu počkať, nastúpiť na druhú diaľnicu v čase ~\(1.41\), čím sa dostane na planétu \(1\) v čase ~\(2.41\), z ktorej ihneď vyrazí a o \(\frac{1}{2.41}\) minút už bude v Polarise – v čase ~\(3.18\). Celé mu to teda trvalo ~\(2.18\) minút. Keby namiesto toho cestoval priamo prvou ďiaľnicou, najskôr by sa na Zenit dostal v čase ~\(3.46\), teda by mu to zabralo ~\(2.46\) minút.