题目描述

考虑带圈的有向图G=(V，E)以及w:E→R，每条边e=(i，j)(ij,i∈V)的权值定义为w[i,j]，令n=|V|。C=(c1,c2,…,ck)(ci∈V)是G中的一个圈当且仅当(c[i],c[i+1])(1<=i<k)和(c[k],c[1])都在E中，这是称k为圈c的长度同时令c[k+1]=c[1]，并定义圈c=(c1,c2,…,ck)的平均值为，即c上所有边的权值的平均值。令为G中所有圈c的平均值的最小值。现在的目标是：在给定了一个图G=(V，E）以及w：E→R之后，请求出G中所有圈c的平均值的最小值

输入格式

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

输出格式

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

样例

样例 1

输入 # 1

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

输出 # 1

3.66666667