Problem1376--PIPI的逃跑路线Ⅲ

1376: PIPI的逃跑路线Ⅲ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 346  Solved: 88
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI费尽千辛万苦终于采集完补血材料满血复活了,但是PIPI越是逃跑,越是发现人类是有极限的,除非超越人类...
PIPI四处打听,得知魔界有n座神殿,神殿之间有m条道路,神器-阎魔刀就藏在第n座神殿。但是魔界之间的道路变换多端,PIPI每经过一条道路,魔界所有的道路长度w就会变成1/(1-w)。并且两座神殿之间,可能没有道路,也可能有多条道路。
如果使用阎魔刀把自己人类面的善性分离,想必就能得到足够击败POPO的“抛瓦”了吧。
于是PIPI打算从魔界的1号神殿出发,请问他寻找到阎魔刀所需要的最短路程。(路程为路径上两点之间的绝对值之和)

Input

第一行输入整数n与m,0<n<=10^5,0<=m<=3*10^5。
接下来m行,每一行三个正整数x,y,w,表示PIPI在1号神殿时,x号神殿与y号神殿有一条道路长为w。其中:x,y<=n,2<=w<=1000。

Output

输出PIPI寻找到阎魔刀的最短路程,保留三位小数。
如果PIPI无法寻找到阎魔刀,输出-1。

Sample Input

3 3
1 2 2
2 3 2
3 1 3

Sample Output

3.000

Source/Category

中等