测试数据来自 system/1966

背景

夜夜很贪玩。

描述

威尼斯是著名的水城。由n个岛和m座桥。岛从1到n编号。
夜夜是一名到威尼斯游玩的游客，她觉得每个岛都很有意思。因此她每次都会随机选择一个与当前岛相邻的岛去参观【同一座岛可以重复参观】。每座桥有一个权值At, 走过这座桥需要花费At个单位的时间, 桥可以双向通过。
夜夜初始在1号岛，她希望最终能到n号岛去。
那么夜夜到达n号岛的期望时间是多少呢？
答案保留一位小数。

格式

输入格式

第一行有两个整数n和m，表示岛屿个数与桥的个数。
之后m行，每行有三个整数u,v和At。其中1<=u,v<=n，表示有一座在岛u和岛v之间的桥，其权值为At。

输出格式

输出答案，答案四舍五入保留到一位小数。

样例1

样例输入1

3 3
1 2 1
2 3 1
3 1 1

样例输出1

2.0

样例2

样例输入2

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

样例输出2

16.0

限制

对于30%的数据
2<=n<=10
对于另外10%的数据
保证数据是一条链
对于另外10%的数据
保证数据是一个环，且1号岛与n号岛相连。
对于100%的数据
2<=n<=200
m<=n(n-1)/2
1<=At<=1000
数据保证每个岛和其余的都是联通的。且图中不存在重边。

每一个测试点时限1秒。