5. Úžasná lyžovačka

Kristína a Aďo sa vybrali na lyžovačku do Tatier. Bohužiaľ, kvôli pandemickým opatreniam sú všetky vleky a lanovky vypnuté. Sú ale odhodlaní lyžovať sa aj za cenu toho, že si budú musieť kopec zakaždým vyšliapať po svojich. Aby sa ale nestratili, budú kráčať po iba po svahoch medzi stanicami lanoviek.

Po prvom výstupe ale zistili, že šliapať do kopca v lyžiarkach je nesmierne náročné, a že čím strmší kopec je, tým viac sú potom vyčerpaní. Aby si ušetrili čo najviac energie na zjazdy, rozhodli sa, že hore radšej pôjdu po čo najmenej strmých kopcoch aj za cenu toho, že ich cesta bude dlhšia.

Samozrejme, ak sa niekde počas ich cesty na vrch objaví úsek na ktorom pôjdu dole kopcom, neváhajú a spustia sa na lyžiach. Je tu ale jeden drobný problém – Aďo je začiatočník a preto nerád jazdí po strmých kopcoch. Chcel by teda, aby aj dole išli po čo najmenej strmých kopcoch.

Zapozerali sa teda do mapy strediska a začali hľadať čo najmenej strmú cestu na kopec, ktorý si vybrali. Stredisko je ale príliš veľké, a tak to po chvíľke vzdali. Keby si tak zobrali so sebou počítač, určite by niečo vymysleli. Ten ale nemajú a preto potrebujú vašu pomoc.

Úloha

Stredisko pozostáva z \(v\) staníc lanoviek, pričom poznáme nadmorské výšky každej z nich. Na jednej z nich, označenej číslom \(s\), stoja Kristína a Aďo, ktorí sa chcú dostať na kopec so stanicou s číslom \(f\).

V stredisku je \(e\) svahov, z ktorých každý spája dve stanice lanoviek, pričom poznáme vzdušnú vzdialenosť staníc ktoré spája. Uvažujeme, že svah je na celom svojom úseku rovnako strmý a jeho strmosť je určená podielom rozdielu prevýšení staníc a jeho vzdušnou vzdialenosťou.

Vašou úlohou je nájsť takú cestu z \(s\) do \(f\), aby maximálna strmosť svahov na tejto ceste bola čo najmenšia.

Formát vstupu

Na prvom riadku dostanete štyri čísla \(v, e, s, f\), kde \(v\) je počet staníc lanoviek, \(e\) je počet svahov v stredisku, \(0 \leq s < v\) je číslo stanice lanovky na ktorej Kristína a Aďo začínajú a \(0 \leq f < v\) je číslo stanice, na ktorú sa chcú dostať. (Stanice lanoviek sú číslované od \(0\).)

Nasleduje \(v\) riadkov, kde každý riadok obsahuje celé číslo \(h_i\) – nadmorskú výšku \(i\)-tej stanice lanovky.

Ďalších \(e\) riadkov obsahuje tri celé čísla \(a_j, b_j, d_j\), kde \(a_j\) a \(b_j\) sú čísla staníc prepojených \(j\)-tým svahom a \(d_j\) je vzdušná vzdialenosť staníc \(a_j\) a \(b_j\).

Formát výstupu

Vypíšte jediné číslo – strmosť najstrmšieho svahu na ceste z \(s\) do \(f\), s presnosťou na práve dve desatinné miesta.

Hodnotenie

Sú 4 sady vstupov. Platia v nich nasledujúce obmedzenia:

Príklad

Input:

4 6 0 3
10
40
50
220
0 1 100
0 2 100
1 2 50
1 3 150
2 3 250
0 3 100

Output:

0.68

Vhodné cesty sú \([0, 1, 2, 3]\) a \([0, 2, 3]\). Obe cesty sú ale rovnako dobré, keďže majú rovnakú najstrmšiu časť – svah medzi stanicami \(2\) a \(3\).