题目描述

原题来自：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)\}\)。

输入格式

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

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

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

输出格式

仅包含一个实数 \(\mu ^*=\min \{ \mu (c) \}\)，要求输出到小数点后 \(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

限制与提示

对于 \(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\)。