题目描述

原题来自：HNOI 2009

考虑带权的有向图 $\red{G=(V,E) }$以及 $\red{w:E→R}$，每条边 $\red{e=(i,j)(i\not =j,i\in V,j\in V)}$的权值定义为 $\red{w_{i,j}}$，令 $\red{n=|V|}$。$\red{c=(c_1​,c_2​,⋯,c_k​)(c_i​∈V) }$是$\red{ G}$ 中的一个圈当且仅当 $\red{(c_i,c_{i+1})(1\le i\lt k) }$和 $\red{(c_k,c_1)}$ 都在 $\red{E }$中，这时称$\red{ k }$为圈$\red{ c }$的长度。同时令$\red{ c_{k+1}=c_1}$，并定义圈$\red{ c=(c_1​,c_2​,⋯,c_k​) }$的平均值为：

$\red{\mu (c)=\frac{1}{k}\sum_{i=1}^k w_{c_i,c_{i+1}}}$

即 $\red{c }$上所有边的权值的平均值。

令 $\red{μ^* (c)=min\{μ(c)\} }$为$\red{ G }$中所有圈$\red{ c }$的平均值的最小值。现在的目标是：在给定了一个图$\red{ G=(V,E) }$以及$\red{w:E→R }$之后，请求出 $\red{G}$ 中所有圈$\red{ c }$的平均值的最小值 $\red{μ^* (c)=min\{μ(c)\}}$。

输入格式

第一行包含两个正整数$\red{ n}$ 和 $\red{m}$，并用一个空格隔开，其中 $\red{n=|V|,m=|E|}$，分别表示图中有$\red{ n }$个顶点和$\red{ m }$条边；

接下来 $\red{m}$ 行，每行包含用空格隔开的三个数 $\red{i,j,w_{i,j}​}$，表示有一条边$\red{ (i,j)}$ 且该边的权值为 $\red{w_{i,j}}$​。

输入数据保证图 $\red{G=(V,E) }$连通，存在圈且有一个点能到达其他所有点。

输出格式

仅包含一个实数 $\red{μ^*=min\{μ(c)\}}$，要求输出到小数点后 $\red{8}$ 位。

样例

输入样例 1

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

输出样例 1

3.66666667

输入样例 2

2 2
1 2 -2.9
2 1 -3.1

输出样例 2

-3.00000000

提示

对于 $\red{20\%}$ 的数据，$\red{≤n≤100,1≤m≤1000；}$

对于 $\red{40\% }$的数据，$\red{1≤n≤1000,1≤m≤5000；}$

对于 $\red{100\% }$的数据，$\red{1\le n\le 3000,1\le m\le 10^4,|w_{i,j}|\le 10^7}$。

输入保证 $\red{1≤i,j≤n}$。