Trevlig väg

문제

När jag går hemåt går jag inte alltid den kortaste vägen, utan en väg som a) hela tiden tar mig närmare hem, och b) är "trevligast", i den meningen att medelvärdet av de passerade vägavsnittens "trevlighetsfaktor" är så hög som möjligt. Skriv ett program som beräknar det maximala sådana medelvärdet.

Kartan över min stad kan beskrivas med hjälp av $nn$ platser numrerade från $11$ till $nn$. Plats $11$ är min startplats och plats $nn$ är mitt hem, och platserna har sorterats efter avstånd så att en plats med högre nummer alltid ligger närmare hemmet än en med lägre nummer.

Vidare finns $mm$ olika "vägavsnitt" som var och en leder från en plats $u_{i}u\_i$ till en annan plats $v_{i}v\_i$ och har en trevlighetsfaktor $w_{i}w\_i$, som kan bero på att där finns några ovanliga träd, någon gullig katt i ett fönster eller något annat trevligt. Eftersom jag alltid vill gå i riktning hemåt, så har vi i beskrivningen endast tagit med vägavsnitt där .

Den som är lite matematiskt intresserad (ifall det nu skulle finnas någon sådan i detta sällskap) skulle kunna kalla detta för en riktad och viktad acyklisk graf.

[이미지 1]

Kartan i det andra exemplet. Den trevligaste vägen är $1\to 3\to 51\backslash rightarrow\; 3\backslash rightarrow\; 5$.

입력

Den första raden innehåller de två heltalen $nn$ och $mm$ ($2\le n\le {10}^{5}2\; \backslash leq\; n\; \backslash leq\; 10^5$ , $1\le m\le 2\cdot {10}^{5}1\; \backslash leq\; m\; \backslash leq\; 2\backslash cdot\; 10^5$). Var och en av de följande $mm$ raderna beskriver ett vägavsnitt och innehåller tre heltal $u_{i}u\_i$, $v_{i}v\_i$ och $w_{i}w\_i$ (, $1\le w_i\le 2\cdot {10}^{6}1\; \backslash le\; w\_i\; \backslash le\; 2\backslash cdot\; 10^6$), vilket betyder att vägavsnittet går från plats $u_{i}u\_i$ till plats $v_{i}v\_i$ och har trevlighetsfaktor $w_{i}w\_i$.

Det kommer aldrig finnas mer än ett vägavsnitt som förbinder samma platser, och det garanteras att det går att ta sig från plats $11$ till plats $nn$.

출력

Skriv ut ett tal: det högsta uppnåbara medelvärdet av trevlighetsfaktorer på en väg från plats 1 till plats $nn$. Svaret anses korrekt om det har ett relativt eller absolut fel av högst ${10}^{-6}10^\{-6\}$.