Problem M
Nice Path

When I go home, I don’t always choose the shortest path, but rather a path that

1. always takes me closer to my home, and

2. 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.

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