Migrated from Lutece 146 Flood

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$N$ villages are connected with $M$ roads, no two villages connected with more than one road.

However, the flood comes, each road has a probability to be submerged, now you should tell us the probability that all the villages are connected (that is from one village, we can reach any other villages with the roads that are not submerged).

Input

In the first line, you will get a number $T$ denotes the number of test case.

For each test case,

In the first line, you will get $2$ number $N$ ($1\leq N\leq 8$) and $M$ ($1\leq M\leq \frac{N\times (N-1)}{2}$), as described above.

In the next $M$ lines, each line contains $3$ numbers $A$, $B$, $C$, indicate there is a road between village $A$ and village $B$ that have a probability of $C$ to be submerged.

Output

For each test case, you should output in a line, give the answer round to $3$ digital.

Samples

1
3 3
1 2 0.2
1 3 0.5
2 3 0.7

0.550

Note

The probability is $0.8\times 0.5\times 0.3\times ($all the $3$ roads are not submerged$) + (0.2\times 0.5\times 0.3+0.8\times 0.5\times 0.3+0.8\times 0.5\times 0.7) ($one of the roads is submerged$) =0.550$

Resources

Sichuan State Programming Contest 2008