【题目描述】
LYC在中国，他开始了到阿布拉斯基索沃尔朗特乎斯德麦尔维的旅行。其间一共有n个点，m条长li的双向边。中国在1点，阿布拉斯基索沃尔朗特乎斯德麦尔维在n点。LYC同学的旅途并不顺利，因为中国到阿布拉斯基索沃尔朗特乎斯德麦尔维的高铁还没有联通，LYC只能骑一只小猫咪去阿布拉斯基索沃尔朗特乎斯德麦尔维。他会按照阿布拉斯基索沃尔朗特乎斯德麦尔维产的阿布拉斯基索沃尔朗特乎斯德麦尔维卫星地图看阿布拉斯基索沃尔朗特乎斯德麦尔维的道路状况以选择到阿布拉斯基索沃尔朗特乎斯德麦尔维的最短路径。因为阿布拉斯基索沃尔朗特乎斯德麦尔维正在革命，为了安全，LYC在走之前，事先了解了到阿布拉斯基索沃尔朗特乎斯德麦尔维所有道路被阻断的可能性pi（sigmapi<=1），并且得知，旅行中最多有一条路径会被阻断（即如果第i条道路被阻断，其他m-1条道路都一定没有被阻断），有1-sigmapi的可能性没有路被阻断。求从中国骑猫到阿布拉斯基索沃尔朗特乎斯德麦尔维期望最短距离（保留七位小数）(如果某次到达不了终点，视作最短路为0)。
【输入格式】
第一行两个整数n，m表示一共有n个点，m条双向边。
接下来m行，每行三个整数，u,v,li,表示u和v之间有li长的路（保证没有自环），和一个七位小数，表示这条路被阻断的可能性pi。
【输出格式】
一个七位小数，表示从中国到阿布拉斯基索沃尔朗特乎斯德麦尔维的期望最短距离。
【样例输入1】
5 4
1 2 1 0.0010000
2 3 3 0.0040000
3 4 5 0.0240000
4 3 2 0.4620000
【样例输出1】
0.0000000
【样例说明1】
无论如何都到不了阿布拉斯基索沃尔朗特乎斯德麦尔维，最短路不存在。
【样例输入2】
5 6
1 2 1 0.1000000
2 3 1 0.1000000
3 4 1 0.1000000
4 5 1 0.1000000
1 5 1 0.1000000
2 4 1 0.1000000
【样例输出2】
1.2000000
【样例说明2】
0.4未切断边，距离1。
0.1切断第1条边，距离1.
0.1切断第2条边，距离1.
0.1切断第3条边，距离1.
0.1切断第4条边，距离1.
0.1切断第5条边，距离3.
0.1切断第6条边，距离1.
总期望距离1.2
【样例输入3】
5 4
1 2 1 0.0010000
2 3 3 0.0040000
3 4 5 0.0240000
4 5 2 0.4620000
【样例输出3】
5.5990000
【样例说明3】这个就不说啦。
【规定】
对于30%的数据n<=100,m<=100
对于50%的数据n<=100,m<=1000
对于100%的数据n<=1000,m<=100000
对于100%的数据0<li<=1000，0<=sigma pi<=1