Minimum Mean Cycle

Given a weighted directed graph \(G=(V,E)\) with a weight function \(w:E\to\mathbb{R}\), where every edge \(e=(i,j)\) (with \(i\neq j,\, i,j\in V\)) has weight \(w_{i,j}\), and \(n=|V|\) is the number of vertices. A cycle in \(G\) is defined as a sequence \(c=(c_1,c_2,\cdots,c_k)\) such that for every \(1\le i < k\), the edge \((c_i,c_{i+1})\) exists in \(E\) and additionally the edge \((c_k,c_1)\) exists, making the sequence a cycle. The length of the cycle is \(k\) and we define \(c_{k+1}=c_1\). The average weight (or mean) of a cycle \(c\) is given by:

\[ \mu(c)=\frac{1}{k}\sum_{i=1}^{k}w_{c_i,c_{i+1}}, \]

Let \(\mu'(G)=\min_{c}\mu(c)\) be the minimum cycle mean over all cycles in \(G\). Your task is to compute \(\mu'(G)\) for the given graph. It is guaranteed that there is at least one cycle in the graph.

Note: The answer should be printed as a floating‐point number with 6 decimal places of precision.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of vertices and edges respectively.

Each of the following \(m\) lines contains three numbers: two integers \(u\) and \(v\) (denoting an edge from vertex \(u\) to vertex \(v\)) and a real number \(w\) representing the weight of that edge.

It is guaranteed that \(u\neq v\) and that at least one cycle exists in the graph.

outputFormat

Output a single line containing the minimum cycle mean \(\mu'(G)\) as a floating-point number rounded to 6 decimal places.

sample

3 3
1 2 3
2 3 4
3 1 5

4.000000