Problem Description

Consider a weighted directed graph \( G = (V, E) \) with a weight function \( w: E \rightarrow \mathbb{R} \). Each edge \( e = (i, j) \) (where \( i \neq j \) and \( i, j \in V \)) has a weight \( w_{i,j} \). Let \( n = |V| \).

A cycle \( c = (c_1, c_2, \cdots, c_k) \) (where \( c_i \in V \)) in \( G \) exists if and only if \( (c_i, c_{i+1}) \) (for \( 1 \le i < k \)) and \( (c_k, c_1) \) are all in \( E \). The length of the cycle \( c \) is \( k \), and we define \( c_{k+1} = c_1 \). The average value of the cycle \( c = (c_1, c_2, \cdots, c_k) \) is defined as
\[ \mu(c) = \frac{1}{k} \sum_{i=1}^{k} w_{c_i, c_{i+1}} \]
which is the average of the weights of all edges in \( c \). Let \( \mu'(G) = \min_c \mu(c) \) be the minimum average value of all cycles \( c \) in \( G \).

Given the graph \( G = (V, E) \) and the weight function \( w: E \rightarrow \mathbb{R} \), find the minimum average value \( \mu'(G) \) of all cycles \( c \) in \( G \).

Input Format

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

The next \( m \) lines each contain three numbers \( i, j, w_{i,j} \), indicating an edge \( (i, j) \) with a weight \( w_{i,j} \). Note that the edge weights can be real numbers. The input data guarantees that the graph \( G = (V, E) \) is connected, contains cycles, and there is a vertex that can reach all other vertices.

Output Format

Output a real number \( \mu'(G) \), accurate to eight decimal places.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3.66666667

Sample Input #2

2 2
1 2 -2.9
2 1 -3.1

Sample Output #2

-3.00000000

Notes

For \( 100\% \) of the data, \( 2 \leq n \leq 3000 \), \( 1 \leq m \leq 10000 \), \( |w_{i,j}| \leq 10^7 \), \( 1 \leq i, j \leq n \), and \( i \neq j \).

Hint: There exists an \( O(nm) \) solution, but an \( O(nm \log n) \) solution can also pass.

见题面 Input 部分

见题面 Output 部分