4611: 最小圈

考虑带权的有向图G=(V,E)以及w:E→R，每条边e=(i,j)(i≠j,i∈V,j∈V)的权值定义为wi,j，令n=|V|。c=(c1,c2,⋯,ck)(ci∈V)是G中的一个圈当且仅当(c_i,c_i+1)(1≤i<k)和(ck,c1)都在E中，这时称k为圈c的长度。同时令c_k+1=c₁，并定义圈c=(c1,c2,⋯,ck)的平均值为：
μ(c)=1/k∑w_ci,ci+1

$\mu (c)=\frac{1}{k}\sum_{i=1}^k w_{c_i,c_{i+1}}$
即c上所有边的权值的平均值。
令μ∗(c)=min{μ(c)}为G中所有圈c的平均值的最小值。现在的目标是：在给定了一个图G=(V,E)以及w:E→R之后，请求出G中所有圈c的平均值的最小值μ∗(c)=min{μ(c)}。

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

仅包含一个实数μ∗=min{μ(c)}，要求输出到小数点后8位

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

3.66666667