绿豆蛙的归宿

题目背景

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

题目描述

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

输入输出格式

输入格式


输入的第一行是两个整数,分别代表图的点数 $n$ 和边数 $m$。 第 $2$ 到第 $(m + 1)$ 行,每行有三个整数 $u, v, w$,代表存在一条从 $u$ 指向 $v$ 长度为 $w$ 的有向边。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

7.00

说明

#### 数据规模与约定 - 对于 $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$,给出的图无重边和自环。