题目描述

给出一个有向无环的连通图，起点为$\red{1}$终点为$\red{N，}$每条边都有一个长度。绿豆蛙从起点出发，走向终点。

到达每一个顶点时，如果有$\red{K}$条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 $\red{1/K }$。

现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入格式

第一行: 两个整数 $\red{N ,M，}$代表图中有$\red{N}$个点、$\red{M}$条边

第二行到第 $\red{1+M }$行: 每行$\red{3}$个整数 $\red{a b c，}$代表从$\red{a}$到$\red{b}$有一条长度为$\red{c}$的有向边

输出格式

从起点到终点路径总长度的期望值，四舍五入保留两位小数。

样例

输入样例

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

输出样例

7.00

提示

对于$\red{20\%}$的数据 $\red{N<=100}$

对于$\red{40\%}$的数据 $\red{N<=1000}$

对于$\red{60\%}$的数据 $\red{N<=10000}$

对于$\red{100\%}$的数据$\red{N<=100000，}$$\red{M<=2\times N}$