As many books, movies and video games had shown us, a zombie outbreak was inevitable. However, all hope is not lost. As usual you've encountered a young girl that has been bitten but not transformed. Therefore, you've escorted her to a medial facility so her blood can be studied and a cure manufactured.

Unfortunately, the medical facility, for obvious reasons, has not been resupplied in a while. The scientists there have asked you to pick several tools, viruses and whatnots, from N places in the city.

Now that you have to go out again, you have created a map with the N + 1 locations: the medical facility (location 0) and the other N where the scientists need you to pick something up (numbered from 1 to N). You've also came up with M two-way paths between some of the locations and the probability to encounter a zombie pack on each of those paths. Note that this is isn't science fiction. If you encounter a zombie pack, you will not survive.

You certainly want to fetch all the items and come back alive. You want to compute the maximal probability of picking every item and coming back to the medical facility (safe and sound) if you take a closed walk (cycle that allows node repetitions).

Input

The input contains several test cases. Each test case begins with two integers, the number of places you have to go to (1 <= N <= 16) and the number of paths you came up with (1 <= M <= N^2), separated by a single space.

The next M lines contain 2 integers and a real number separated by spaces. Two integers ui and vi (0 <= ui, vi <= N and ui<>vi) are the locations this path connects. Real number pi (0 <= pi <= 1) represents the probability that you will encounter a zombie pack along this path.

You may assume that, for all i <> j, probabilities pi and pj are independent from each other.

The end of input is indicated by a test case with N = M = 0 and should not be processed

Output

For each test case output a single line with a single real number: the probability of getting back to the medical facility alive with all items. Round the result to exactly three places after decimal point. If there's no way to pick all items, you should output 0.000.

Example

Input:
2 3
0 1 0.3
0 2 0.4
1 2 0.2
2 3
0 1 0.3
0 2 0.5
1 2 0.1
2 2
0 1 0.1
0 1 0.9
2 3
0 1 0.92
0 2 0.92
1 2 0.92
2 3
0 1 0.92
0 2 0.92
1 2 0.93
0 0

Output:
0.336
0.397
0.000
0.001
0.000