分数规划问题

求分数的最值问题，给出每个物品的两个权值 $a_i$ 和 $b_i$ ,让

\frac{\sum{a_i}}{\sum{b_i}}

\frac{\sum{w_ia_i}}{\sum{w_ib_i}} \ge x

\sum{w_i{\sdot}(a_i-xb_i)} \ge 0

\mu(c)= \frac 1 k \sum\limits{i=1}^{k} w{ci,c{i+1}}

$$
即 $c$ 上所有边的权值的平均值。设 $\mu’(G)=\min_c\mu(c)$ 为 $G$ 中所有圈 $c$ 的平均值的最小值。

给定图 $G=(V,E)$ 以及 $w:E\rightarrow \R$，求出 $G$ 中所有圈 $c$ 的平均值的最小值 $\mu’(G)$。

输入格式

第一行两个正整数，分别为 $n$ 和 $m$，并用一个空格隔开。其中 $n=|V|$，$m=|E|$ 分别表示图中有 $n$ 个点 和 $m$ 条边。

接下来 $m$ 行，每行三个数 $i,j,w{i,j}$，表示有一条边 $(i,j)$ 且该边的权值为 $w{i,j}$，注意边权可以是实数。输入数据保证图 $G=(V,E)$ 连通，存在圈且有一个点能到达其他所有点。

输出格式

一个实数 $\mu’(G)$，要求精确到小数点后 $8$ 位。

样例 #1

样例输入 #1

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

样例输出 #1

1
3.66666667

样例 #2

样例输入 #2

1
2
3
2 2
1 2 -2.9
2 1 -3.1

样例输出 #2

1
-3.00000000

提示

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