Description

给出一个有向图，求这个图的路径长度平均值最小的环。

Input Format

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

Output Format

仅包含一个实数∮（C）=MIN{∮(C)},要求输出到小数点后8位。

Sample

输入样例1：

2 2
1 2 -2.9
2 1 -3.1

输出样例1：

-3.00000000 

输入样例2：

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

输出样例2：

3.66666667 

Hint

20%的数据：n<=100.m<=1000; 50%的数据：n<=1000.m<=5000; 100%的数据：n<=3000.m<=10000; 1000%的数据：|W(i,j)|<=10^7.