题目描述

Jerry是一个很强大但是很有爱的人。

Jerry现在在$TJ$市，他希望想去$YT$市，但是不知道如何去才是最近的。

但是他现在在工作，于是求助于你，并规定了一些要求。

Jerry会给你城市地图，即Jerry所知道的$N$个城市和$M$条道路。

Jerry所在世界是很奇妙的，在Jerry每从一个城市到达另一个城市，所有城市之间的道路长度$w_i$都会变为$\frac{1}{1-w_i}$，即$w_i \larr \frac{1}{1-w_i}$。

规定Jerry所在的城市序号为 $1$ ，想要到达的城市为 $N$，求在该世界中从 $1$ 到 $N$ 的最短路。

因为 Jerry 喜欢非负数，所以他只需要你输出经过的边权权值绝对值之和最小的那个值就可以了。

输出答案保留三位小数。

输入

第一行两个正整数 $N,M$，表示这个城市个数和道路个数。

接下来 $M$ 行，每行三个正整数 $u,v,w$，表示存在一条连接点 $u,v$ 的无向边，且初始权值为 $w$。

输出

如果能到达的话，输出边权绝对值之和最小的答案，保留三位小数。

否则请输出 $-1$。

样例

3 3
1 2 2
2 3 2
3 1 3

3.000

样例说明

走 $1→2→3$，总花费 $2+∣\frac{1}{1−2}∣=3$。

数据范围

$n≤100000,m≤300000,2≤w_i≤1000$