Problem Statement

When friends are talking with each other, it sometimes happens that another pair of friends starts talking about the same topic. Let us model this in a competitive-programming style.
There are N friend groups, numbered from 0 to $N-1$.
There are a total of $M$ relations among these friend groups, each represented by integers $A$, $B$, $C$. This means: "When group $A$ is talking about a certain topic, the people in group $B$ start talking about that topic with a probability of $C$ percent."

Now the people in group 0 have started a conversation about yukicoder.
Find the probability that the people in group $N-1$ start talking about yukicoder.

Input

$N$ $M$
$A_1$ $B_1$ $C_1$
⋮
$A_M$ $B_M$ $C_M$

The first line gives the number of groups $N$ and the number of relations between groups $M$. $ 1 \leq N \leq 20$, $1 \leq M \leq N(N-1)/2 $
Each of the next $M$ lines gives three integers $A$, $B$, $C$. Their meaning is as described above. $ 0 \leq A_i \leq N-1 $, $0 \leq B_i \leq N-1$, $1 \leq C_i \leq 100$
$A_i \neq B_i$, and $(A_i, B_i) \neq (A_j, B_j)$ when $i \neq j$.
The input guarantees that a topic started by a group is never transmitted and returned to that same group.
The probability for any pair with no defined relation is taken to be 0.

Output

Output the probability that the friends in group $N-1$ start talking about yukicoder.
The output must not have an absolute error exceeding $10^{-6}$.
Print a newline at the end.

Sample

4 4
0 1 100
0 2 100
1 3 50
2 3 50

0.75

4 4
0 1 50
0 2 50
1 3 50
2 3 50

0.4375