3220 - 最小圈
时间限制 : 1 秒
内存限制 : 128 MB
考虑带圈的有向图G=(V，E)以及w:E→R，每条边e=(i，j)(i<>j,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位。
输入/输出样例
输入格式
4 5 1 2 5 2 3 5 3 1 5 2 4 3 4 1 3
输出格式
3.66666667
提示
【样例说明】
<span style="font-family:宋体;">样例</span><span>1</span><span style="font-family:宋体;">中共有</span><span>2</span><span style="font-family:宋体;">个圈</span><span>(1,2,3)</span><span style="font-family:宋体;">和</span><span>(1,2,4)</span><span style="font-family:宋体;">。其中第一个圈的平均值为</span><span>5</span><span style="font-family:宋体;">，第二个圈的平均值为</span><span>11/3</span><span style="font-family:宋体;">。样例</span><span>2</span><span style="font-family:宋体;">中存在一个负圈。</span><span></span>
<span style="font-family:宋体;">【数据范围及约定】</span><span></span>
<span>20%</span><span style="font-family:宋体;">的数据：</span><span>n<=100,m<=1000</span><span style="font-family:宋体;">；</span><span></span>
<span>50%</span><span style="font-family:宋体;">的数据：</span><span>n<=1000,m<=5000</span><span style="font-family:宋体;">；</span><span></span>
<span>100%</span><span style="font-family:宋体;">的数据：</span><span>n<=3000,m<=10000</span><span style="font-family:宋体;">；</span><span></span>
<span>100%</span><span style="font-family:宋体;">的数据：</span><span>|w[i,j]|<=10^7</span><span style="font-family:宋体;">。</span><span></span>