Problem E: Reliability

A small district in a rural area contains a few villages (maximum 15), which are well-separated from each other. There are no roads in the district but the villagers have created mud tracks between some pairs of villages. There are at most 25 such tracks and between a given pair of villages there is at most one track. Unfortunately, during the rainy season, some tracks may get flooded and become unusable. Each track may or may not get flooded independent of any other track. For every track, the probability that it is usable (not flooded) is given. The district is connected if there is a way to reach any village from any other village using tracks which are not flooded. You have to write a program that is given as input the probability for each track to be flooded. Your program must determine the probability that the district is connected.

Input

The input will consist of several test cases. For every case, the first line will contain a single integer $n$, the number of villages. If $n$ is 0, it indicates end of input. The villages are assumed to be numbered from 0 to $n$-1. The next line will contain $m$, the number of tracks. The next $m$ lines will each contain 3 numbers, two integers and a fraction, separated by a space. The first two integers specify the villages that are connected by the track and the third number is the probability that the track is usable. This will be a decimal fraction between 0.0 and 1.0, with only one digit after the decimal point. There will be no lines separating consecutive test cases.

Output

The output for each test case must a single number, written on a separate line for each case. This number must be accurate to 3 decimal places and at most 3 digits after the decimal point should be printed.

Sample Input

2
1
0 1 0.3
3
3
0 1 0.5
0 2 0.5
1 2 0.5
0

Sample Output

0.3
0.5