[HNOI2009] 最小圈

题目描述

考虑带权的有向图 $G=(V,E)$ 以及 $w:E\rightarrow R$,每条边 $e=(i,j)(i\neq 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<k)$ 和 $(c_k,c_1)$ 都在 $E$ 中，这时称 $k$ 为圈 $c$ 的长度同时令 $c_{k+1}=c_1$，并定义圈 $c=(c_1,c_2,\cdots,c_k)$ 的平均值为 $\mu(c)=\dfrac{\sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}}{k}$，即 $c$ 上所有边的权值的平均值。令 $\mu'(c)=Min(\mu(c))$ 为 $G$中所有圈 $c$ 的平均值的最小值。现在的目标是：在给定了一个图 $G=(V,E)$ 以及 $w:E\rightarrow R$ 之后，请求出 $G$ 中所有圈 $c$ 的平均值的最小值 $\mu'(c)=Min(\mu(c))$

输入格式

第一行2个正整数，分别为 $n$ 和 $m$，并用一个空格隔开，只用 $n=|V|,m=|E|$ 分别表示图中有 $n$ 个点 $m$ 条边。 接下来 $m$ 行，每行3个数 $i,j,w_{i,j}$，表示有一条边 $\langle i,j\rangle$ 且该边的权值为 $w_{i,j}$。输入数据保证图 $G=(V,E)$ 连通，存在圈且有一个点能到达其他所有点。

输出格式

请输出一个实数 $\mu'(c)=Min(\mu(c))$，要求输出到小数点后8位。

样例 #1

样例输入 #1

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

样例输出 #1

3.66666667

样例 #2

样例输入 #2

2 2
1 2 -2.9
2 1 -3.1

样例输出 #2

-3.00000000

提示

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