[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

输入输出格式

输入格式


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

输出格式


请输出一个实数$\mu'(c)=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

说明

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