题目描述

给定一个$n$个点$m$条边的有向无环图，起点为$1$，终点为$n$，每条边有长度，保证从起点可以到达所有的点，所有的点都能够到达终点。

现在从起点出发开始随机游走，每在一个顶点时，记该节点出度为$k$，则可以选择任意一条边离开该点，走向每条边的概率为$\frac{1}{k}$。

现在，请你求出从起点出发走到终点的路径总长度期望。

输入格式

第一行输入两个整数$n,m$。 接下来$m$行，每行输入三个整数$u,v,w$，表示一条$u\rightarrow v$，长度为$w$的有向边。

输出格式

输出一行一个实数，表示你的答案，四舍五入保留两位小数。

样例输入 #1

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

样例输出 #1

7.00

说明/提示

有$1\leq n\leq 10^5,1\leq m\leq 5\times 10^5,1\leq w\leq 10^9$。