Description

Original source: HNOI 2009

Consider a weighted directed graph $G=(V,E)$ with $w:E\to R$, where each edge $e=(i,j)(i\not =j,i\in V,j\in V)$ has a weight defined as $w_{i,j}$. Let $n=|V|$. A cycle $c=(c_1,c_2,\cdots ,c_k)(c_i\in V)$ in $G$ exists if and only if both $(c_i,c_{i+1})(1\le i\lt k)$ and $(c_k,c_1)$ are in $E$, where $k$ is called the length of cycle $c$. Let $c_{k+1}=c_1$, and define the average value of cycle $c=(c_1,c_2,\cdots ,c_k)$ as:

That is, the average of the weights of all edges in $c$.

Let $\mu^*(c)=\min \{\mu (c)\}$ be the minimum average value among all cycles $c$ in $G$. The goal is: given a graph $G=(V,E)$ and $w:E\to R$, compute the minimum average value $\mu ^* (c)=\min \{ \mu (c)\}$ of all cycles $c$ in $G$.

Input Format

The first line contains two positive integers $n$ and $m$, separated by a space, where $n=|V|$ and $m=|E|$, representing the number of vertices and edges in the graph, respectively.

The next $m$ lines each contain three space-separated numbers $i,j,w_{i,j}$, indicating an edge $(i,j)$ with weight $w_{i,j}$.

The input guarantees that the graph $G=(V,E)$ is connected, contains at least one cycle, and has at least one vertex that can reach all other vertices.

Output Format

Output only one real number $\mu ^*=\min \{ \mu (c) \}$, rounded to 8 decimal places.

Sample 1

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

3.66666667

Sample 2

2 2
1 2 -2.9
2 1 -3.1

-3.00000000

Data Range and Hints

For $20\%$ of the data, $1\le n\le 100,1\le m\le 1000$;
For $40\%$ of the data, $1\le n\le 1000,1\le m\le 5000$;
For $100\%$ of the data, $1\le n\le 3000,1\le m\le 10^4,|w_{i,j}|\le 10^7$.

The input ensures $1\le i,j\le n$.