8977: 洛谷P4316 - 绿豆蛙的归宿
[Creator : ]
Description
随着新版百度空间的上线，Blog 宠物绿豆蛙完成了它的使命，去寻找它新的归宿。
给出张 $n$ 个点 $m$ 条边的有向无环图，起点为 $1$，终点为 $n$，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。
绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 $k$ 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 $\frac{1}{k}$ 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
给出张 $n$ 个点 $m$ 条边的有向无环图，起点为 $1$，终点为 $n$，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。
绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 $k$ 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 $\frac{1}{k}$ 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
Input
输入的第一行是两个整数，分别代表图的点数 $n$ 和边数 $m$。
第 $2$ 到第 $(m + 1)$ 行，每行有三个整数 $u, v, w$，代表存在一条从 $u$ 指向 $v$ 长度为 $w$ 的有向边。
第 $2$ 到第 $(m + 1)$ 行，每行有三个整数 $u, v, w$，代表存在一条从 $u$ 指向 $v$ 长度为 $w$ 的有向边。
Output
输出一行一个实数代表答案，四舍五入保留两位小数。
Constraints
对于 $20\%$ 的数据，保证 $n \leq 10^2$。
对于 $40\%$ 的数据，保证 $n \leq 10^3$。
对于 $60\%$ 的数据，保证 $n \leq 10^4$。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times n$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^9$，给出的图无重边和自环。
对于 $40\%$ 的数据，保证 $n \leq 10^3$。
对于 $60\%$ 的数据，保证 $n \leq 10^4$。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times n$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^9$，给出的图无重边和自环。
Sample 1 Input
4 4
1 2 1
1 3 2
2 3 3
3 4 4
Sample 1 Output
7.00