6987: 「一本通 3.3 练习 1」最小圈
[Creator : ]
Description
原题来自：HNOI 2009
考虑带权的有向图 $G=(V,E)$ 以及 $w:E\to R$，每条边 $e=(i,j)(i\not =j,i\in V,j\in V)$ 的权值定义为 $w_{i,j}$，令 n=|V|。$c=(c_1,c_2,\cdots ,c_k)(c_i\in V)$ 是 $G$ 中的一个圈当且仅当 $(c_i,c_{i+1})(1\le i\lt k)$ 和 $(c_k,c_1)$ 都在 $E$ 中，这时称 $k$ 为圈 $c$ 的长度。同时令 $c_{k+1}=c_1$，并定义圈 $c=(c_1,c_2,\cdots ,c_k)$ 的平均值为：
$\mu (c)=\frac{1}{k}\sum_{i=1}^k w_{c_i,c_{i+1}}$
即 $c$ 上所有边的权值的平均值。
令 $\mu^*(c)=\min \{\mu (c)\}$ 为 $G$ 中所有圈 $c$ 的平均值的最小值。现在的目标是：在给定了一个图 $G=(V,E)$ 以及 $w:E\to R$ 之后，请求出 $G$ 中所有圈 $c$ 的平均值的最小值 $\mu ^* (c)=\min \{ \mu (c)\}$。
考虑带权的有向图 $G=(V,E)$ 以及 $w:E\to R$，每条边 $e=(i,j)(i\not =j,i\in V,j\in V)$ 的权值定义为 $w_{i,j}$，令 n=|V|。$c=(c_1,c_2,\cdots ,c_k)(c_i\in V)$ 是 $G$ 中的一个圈当且仅当 $(c_i,c_{i+1})(1\le i\lt k)$ 和 $(c_k,c_1)$ 都在 $E$ 中，这时称 $k$ 为圈 $c$ 的长度。同时令 $c_{k+1}=c_1$，并定义圈 $c=(c_1,c_2,\cdots ,c_k)$ 的平均值为：
$\mu (c)=\frac{1}{k}\sum_{i=1}^k w_{c_i,c_{i+1}}$
即 $c$ 上所有边的权值的平均值。
令 $\mu^*(c)=\min \{\mu (c)\}$ 为 $G$ 中所有圈 $c$ 的平均值的最小值。现在的目标是：在给定了一个图 $G=(V,E)$ 以及 $w:E\to R$ 之后，请求出 $G$ 中所有圈 $c$ 的平均值的最小值 $\mu ^* (c)=\min \{ \mu (c)\}$。
Input
第一行包含两个正整数 n 和 m，并用一个空格隔开，其中 $n=|V|,m=|E|$，分别表示图中有 n 个顶点和 m 条边；
接下来 m 行，每行包含用空格隔开的三个数 $i,j,w_{i,j}$，表示有一条边 $(i,j)$ 且该边的权值为 $w_{i,j}$。
输入数据保证图 G=(V,E) 连通，存在圈且有一个点能到达其他所有点。
接下来 m 行，每行包含用空格隔开的三个数 $i,j,w_{i,j}$，表示有一条边 $(i,j)$ 且该边的权值为 $w_{i,j}$。
输入数据保证图 G=(V,E) 连通，存在圈且有一个点能到达其他所有点。
Output
仅包含一个实数 $\mu ^*=\min \{ \mu (c) \}$，要求输出到小数点后 8 位。
Constraints
对于 $20\%$ 的数据，$1\le n\le 100,1\le m\le 1000$；
对于 $40\%$ 的数据，$1\le n\le 1000,1\le m\le 5000$；
对于 $100\%$ 的数据，$1\le n\le 3000,1\le m\le 10^4,|w_{i,j}|\le 10^7$。
输入保证 $1\le i,j\le n$。
对于 $40\%$ 的数据，$1\le n\le 1000,1\le m\le 5000$；
对于 $100\%$ 的数据，$1\le n\le 3000,1\le m\le 10^4,|w_{i,j}|\le 10^7$。
输入保证 $1\le i,j\le n$。
Sample 1 Input
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
Sample 1 Output
3.66666667
Sample 2 Input
2 2
1 2 -2.9
2 1 -3.1
Sample 2 Output
-3.00000000