Problem D
Get Shorty

Nils and Mikael are intergalaxial fighters as well as lethal enemies. Now Nils has managed to capture the poor Mikael in his dark dungeons, and it is up to you to help Mikael escape with as much of his pride intact as possible.

The dungeons can be viewed as a set of corridors and intersections. Each corridor joins two intersections. There are no guards, traps, or locked doors in Nils’ dungeon. However, there is one obstacle which makes escaping from the dungeon a perilious project: in each corridor there is a sentry, armed with a factor weapon. (As is commonly known, a factor weapon with factor $f$ reduces the size of its target to a factor $f$ of its original size, e.g. if Mikael is $8$ gobs large and is hit by a factor weapon with factor $f = 0.25$ his size will be reduced to $2$ gobs.)

Mikael will not be able to pass through a corridor without being hit by the factor weapon (but luckily enough, reloading the factor weapon takes enough time that the sentry will only have time to shoot him once as he passes through). It seems inevitable that Mikael will come out of this adventure a smaller man, but since the sentries have different factors in their factor weapons, his final size depends very much on the route he takes to the exit of the dungeons. Naturally, he would like to lose as little size as possible, and has asked you to help him accomplish that.

Input

Input consists of a series of test cases (at most $20$). Each test case begins with a line consisting of two integers $n$, $m$ separated by a single space, where $2 \le n \le 10\, 000$ is the number of intersections and $1 \le m \le 15\, 000$ is the number of corridors in Nils’ dungeon. Then follow $m$ lines, each containing two integers $x$, $y$ and a real number $f$ (with at most four decimals), indicating that there is a corridor between intersections $x$ and $y$, and that the factor weapon of the sentry in that corridor has factor $0 \le f \le 1$. Intersections are numbered from $0$ to $n-1$. Mikael always starts in intersection $0$, and the exit is located in intersection $n-1$.

The last case will be followed by a case where $n = m = 0$, which should not be processed.

Output

For each test case, output a single line containing a real number (with exactly four decimals) indicating how big a fraction of Mikael will be left when he reaches the exit, assuming he chooses the best possible route through the dungeon. You may assume that it is always possible for Mikael to reach the exit.

3 3
0 1 0.9
1 2 0.9
0 2 0.8
2 1
1 0 1
0 0

0.8100
1.0000