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
$n1$. Mikael always
starts in intersection $0$, and the exit is located in
intersection $n1$.
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.
Sample Input 1 
Sample Output 1 
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
