题目描述

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

一只小蛙从起点出发，走向终点。到达每一个顶点时，如果该节点有 $k$ 条出边，小蛙会等概率地选择其中一条边离开该点（每条边被选中的概率为 $\frac{1}{k}$）。

小蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？

输入格式

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

第 $2$ 到第 $(m + 1)$ 行，每行三个整数 $u, v, w$，表示存在一条从 $u$ 指向 $v$、长度为 $w$ 的有向边。

输出格式

输出一行一个实数，表示路径总长度的期望值，四舍五入保留两位小数。

样例

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

7.00

提示

对于 $20\%$ 的数据，保证 $n \le 10^2$。

对于 $40\%$ 的数据，保证 $n \le 10^3$。

对于 $60\%$ 的数据，保证 $n \le 10^4$。

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$，$1 \le m \le 2 \times n$，$1 \le u, v \le n$，$0 \le w \le 10^9$，给出的图无重边和自环。