513009 - 旅客

【题目描述】旅客(passenger)

有一个n个点m条边的无重边无自环的有向无环图,一名旅客从节点1出发(节点1可以到达所有的点),走到终点n(所有的点都可以到达终点n),已知每一个节点如果有k条出边,则他选择每条出边的概率为1/k。求他所经过的路径总长度的期望值。

输入

第一行为两个整数n和m(1≤n≤100000,1≤m≤2×n)。 第2到第(m+1)行,每行有三个整数u,v,w(1≤u,v≤n,1≤w≤1000000000),代表节点u到节点v有一条长度为w的有向边。

输出

输出一个实数(四舍五入保留两位小数)。

样例

输入

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

输出

7.00
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题