問題文

友達同士で話をしていると,別の友達どうしが,同じ話題で話し始めることがあります。これを競プロっぽくモデル化してみましょう。
N個の友達グループがあり,これらのグループはそれぞれ数字0から$N-1$までの番号がつけられています。
また,これらの友達グループ同士には,合計で$M$個の関係があり,それぞれは整数$A$, $B$, $C$で表されるとします。これは「グループ$A$がある話題を話していると,グループ$B$の人たちは$C$パーセントの確率でその話題を始める」ということを表しています。

今グループ0の人達がyukicoderについて会話を始めました。
この時,グループ$N-1$の人達がyukicoderについて話し始める確率を求めてください。

入力

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

グループの数$N$,グループ同士の関係の数$M$が1行目に与えられます。 $1\le N\le 20$, $1\le M\le N(N-1)/2$
次の$M$行にはそれぞれ3つの整数$A$,$B$,$C$が与えられます。この意味は上に示したとおり。 $0\le A_i\le N-1$, $0\le B_i\le N-1$, $1\le C_i\le 100$
$A_i\ne B_i$であり,また$i\ne j$のとき$(A_i,B_i)\ne (A_j,B_j)$である。
入力では,あるグループが始めた話題が伝達してそのグループにまた同じ話題が戻ってくることは無いことが保証されている。
関係が定義されてないところの確率は0であるとする。

出力

グループ$N-1$の友達同士がyukicoderについて話しはじめる確率を出力してください。
出力は${10}^{-6}$を超える絶対誤差を含んではいけません。
最後に改行してください。

サンプル

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