题目描述

    雨后的Poetic Island空气格外清新,于是Freda和Rainbow出来散步。Poetic Island的交通可以看作一张n个点、m条边的有向无环图。由于刚下过雨,每条边都有一个积水深度,而恰好Freda和Rainbow都喜欢踩水玩儿,于是Ta们从某个点出发,选择走向哪条边的概率与该边的积水深度是成正比的。即:如果Freda和Rainbow现在在点u,点u出发的所有边的积水深度之和为s,从u到v的边积水深度为w,那么Ta们选择走向v的概率就是w/s。Ta们会一直走下去,直到到达一个没有出边的点,那么散步的路程长度就是走过的边的数量。

   更特殊的是,Freda和Rainbow在出发之前还可以选择一条边,在散步过程中无视这条边的存在(当然也可以不选择)。请你帮忙计算一下,Ta们从0号点出发,散步的路程长度的期望值最大是多少?(就是问你删除哪条边之后,在剩下的图中散步的路程长度期望值最大。)

输入格式

第一行两个正整数n、m。

接下来m行每行三个整数u、v、w,表示从u到v有一条有向边,积水深度为w。

输出格式

输出Freda和Rainbow散步的路程长度的最大期望值,四舍五入保留六位小数。

样例输入1

4 5

0 1 2

0 2 1

0 3 3

1 3 1

2 3 4

样例输出1

2.000000

样例输入2

9 8

0 1 1

1 2 1

2 3 1

0 4 2

4 5 10

4 6 1

6 7 1

7 8 1

样例输出2

3.666667

数据范围与约定

对于 30% 的数据,2<=n<=100,1<=m<=1000。

对于 100% 的数据,2<=n<=10000,1<=m<=100000,0<=u,v<n,1<=w<=1000。