最小圈

题号：NC50384
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

考虑带权的有向图G=(V,E)以及 $w:E \to R$ ，每条边 $e=(i,j)(i \not=j,i \in V,j \in V)$ 的权值定义为 $w_{i,j}$ ，令n=|V|。 $c=(c_1,c_2, \cdots,c_k)(c_i \in V)$ 是G中的一个圈当且仅当 $(c_i,c_{i+1})(1 \le i \lt k)$ 和 $(c_k,c_1)$ 都在E中，这时称k为圈c的长度。同时令 $c_{k+1}=c_1$ ，并定义圈 $c=(c_1,c_2, \cdots,c_k)$ 的平均值为：
$\mu(c)= \frac{1}{k} \sum_{i=1}^kw_{c_i,c_{i+1}}$
即c上所有边的权值的平均值。
令 $\mu^*(c)= \min \{ \mu(c) \}$ 为G中所有圈c的平均值的最小值。现在的目标是：在给定了一个图G=(V,E)以及 $w:E \to R$ 之后，请求出G中所有圈c的平均值的最小值 $\mu^*(c)= \min \{ \mu(c) \}$ 。

输入描述:

第一行包含两个正整数n和m，并用一个空格隔开，其中n=|V|,m=|E|，分别表示图中有n个顶点和m条边；
接下来m行，每行包含用空格隔开的三个数，表示有一条边(i,j)且该边的权值为。
输入数据保证图G=(V,E)连通，存在圈且有一个点能到达其他所有点。

输出描述:

仅包含一个实数，要求输出到小数点后8位。

示例1

输入

复制

输出

复制

3.66666667

示例2

输入

复制

2 2
1 2 -2.9
2 1 -3.1

输出

复制

-3.00000000

备注:

对于的数据，；
对于的数据，；
对于的数据，。
输入保证。