#282. 绿豆蛙的归宿

绿豆蛙的归宿

绿豆蛙的归宿

题目背景

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

题目描述

给出张 nn 个点 mm 条边的有向无环图,起点为 11,终点为 nn,每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。

绿豆蛙从起点出发,走向终点。 到达每一个顶点时,如果该节点有 kk 条出边,绿豆蛙可以选择任意一条边离开该点,并且走向每条边的概率为 1k\frac{1}{k} 。现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?

输入格式

输入的第一行是两个整数,分别代表图的点数 nn 和边数 mm

22 到第 (m+1)(m + 1) 行,每行有三个整数 u,v,wu, v, w,代表存在一条从 uu 指向 vv 长度为 ww 的有向边。

输出格式

输出一行一个实数代表答案,四舍五入保留两位小数。

样例 #1

样例输入 #1

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

样例输出 #1

7.00

提示

数据规模与约定

  • 对于 20%20\% 的数据,保证 n102n \leq 10^2
  • 对于 40%40\% 的数据,保证 n103n \leq 10^3
  • 对于 60%60\% 的数据,保证 n104n \leq 10^4
  • 对于 100%100\% 的数据,保证 1n1051 \leq n \leq 10^51m2×n1 \leq m \leq 2 \times n1u,vn1 \leq u, v \leq n1w1091 \leq w \leq 10^9,给出的图无重边和自环。