Problem M
Nice Path
Languages
en
sv
When I go home, I don’t always choose the shortest path, but rather a path that

always takes me closer to my home, and

is ”nicest”, in the sense that the average ”niceness factor” of the path segments I pass is as high as possible.
Write a program that computes the maximum such average.
The map of my city can be described by $n$ places numbered from $1$ to $n$. Place $1$ is where I start, and place $n$ is my home. All places are sorted by the distance to my home, so a place with a higher number is always closer to my home than one with a lower number.
Furthermore, there are $m$ different path segments that each lead from one place $u_ i$ to another place $v_ i$ and has a niceness factor of $w_ i$. The niceness factor could depend on for example whether the path segment contains some rare trees, a cute cat sitting in a window or some other nice thing. Since I always want to go home, the description only includes path segments where $u_ i < v_ i$.
If you are mathematically inclined, we might call this a directed, weighted, acyclic graph.
Input
The first line consists of the integers $n$ and $m$ ($2 \leq n \leq 10^5$, $1 \leq m \leq 2\cdot 10^5$), the number of places and the number of path segments.
Each of the following $m$ lines describe a path segment and consists of the three integers $u_ i$, $v_ i$ and $w_ i$ ($1 \leq u_ i < v_ i \leq n$, $1 \le w_ i \le 2\cdot 10^6$), which means that a path segment goes from place $u_ i$ to place $v_ i$ with a niceness factor of $w_ i$.
There will never be more than one path segment connecting two places, and it’s guaranteed that it’s possible to get from place $1$ to place $n$.
Output
Output a single number: the highest possible average niceness factor on a path from place $1$ to place $n$. Your answer will be considered correct if its relative or absolute error is at most $10^{6}$.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.
Group 
Points 
Constraints 
$1$ 
$21$ 
$2 \le n \le 10$, $1 \le m \le 20$ 
$2$ 
$41$ 
$2 \le n \le 1000$, $1 \le m \le 2000$ 
$3$ 
$28$ 
No additional constraints. 
Sample Input 1  Sample Output 1 

3 3 1 2 20 2 3 17 1 3 18 
18.5000000000 
Sample Input 2  Sample Output 2 

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