#3036. 绿豆蛙的归宿

绿豆蛙的归宿

题目描述

随着新版百度空间的下线,Blog 宠物绿豆蛙完成了它的使命,去寻找它新的归宿。

给出一个有向无环的连通图,起点为 1 1 终点为 n n ,每条边都有一个长度。绿豆蛙从起点出发,走向终点。

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

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

输入格式

第一行: 两个整数 n,m n,m ,代表图中有 n n 个点、 m m 条边。

第二行到第 1+m 1+m 行: 每行 3 个整数 a,b,c a,b,c ,代表从 a a b b 有一条长度为 c c 的有向边。

输出格式

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

样例输入

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

样例输出

7.00

数据规模与约定

对于 100%100\% 的数据,n1×105 n\leq 1\times 10^5 m2n m\leq 2n

题目来源

Poetize3