【例题3】路径长度

题目描述

给出一张 $n$ 个点 $m$ 条边的有向无环图，起点为 $1$ ，终点为 $n$ ，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

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

第一行有两个整数，分别代表图的点数 $n$ 和边数 $m$ 。

接下来 $m$ 行，每行有三个整数 $u$ , $v$ , $w$ ，代表存在一条从 $u$ 指向 $v$ 长度为 $w$ 的有向边。

输出一个实数，表示答案，保留两位小数。

对于 $20\%$ 的数据，保证 $n \leq 10^{2}$ ；
对于 $40\%$ 的数据，保证 $n \leq 10^{3}$ ；
对于 $60\%$ 的数据，保证 $n \leq 10^{4}$ ；
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^{5}$ ， $1 < m < 2n$ ， $1 \leq u,v \leq n$ ， $1 \leq w \leq 10^{9}$ ，给出的图无重边和自环。

7.00