Problem E
Trevlig väg

När jag går hemåt går jag inte alltid den kortaste vägen, utan en väg som

1. hela tiden tar mig närmare hem, och

2. ä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 $n$ platser numrerade från $1$ till $n$. Plats $1$ är min startplats och plats $n$ ä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 $m$ olika vägavsnitt som var och en leder från en plats $u_ i$ till en annan plats $v_ i$ och har en trevlighetsfaktor $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 $u_ i<v_ i$.

Den som är lite matematiskt intresserad skulle kunna kalla detta för en riktad och viktad acyklisk graf.

Indata

Den första raden innehåller de två heltalen $n$ och $m$ ($2 \leq n \leq 10^5$ , $1 \leq m \leq 2\cdot 10^5$), antalet platser och antalet vägavsnitt.

Var och en av de följande $m$ raderna beskriver ett vägavsnitt och innehåller tre heltal $u_ i$, $v_ i$ och $w_ i$ ($1 \leq u_ i < v_ i \leq n$, $1 \le w_ i \le 2\cdot 10^6$), vilket betyder att vägavsnittet går från plats $u_ i$ till plats $v_ i$ och har trevlighetsfaktor $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 $1$ till plats $n$.

Utdata

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

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

3 3
1 2 20
2 3 17
1 3 18

18.5000000000

5 6
1 2 20
2 3 17
1 3 18
4 5 19
3 5 23
2 4 22

20.5000000000