Cooperative game P74845

Competitions are not in fashion anymore. What is fashionable now are cooperative games, where the participants collaborate to achieve a common goal. So, n friends get inspired by the chain game, in which an array of people whisper a message M in order from one extreme to the other one, trying that M gets not corrupted on the way. But, to make the game more fun, some changes are made:

Let x be the initial transmitter of M, and let y be the final receiver. At each step of the game, the person u that just got M (or x, if it is the first round) must choose another person v and transmit M to him or her. For every pair (u, v), we know the probability p_uv that the direct transmision of the message from u to v is correct. That probability is independent of the round. A corrupted message never gets recovered. The game ends when M reaches y.

Playing optimally, what is the probability that M gets correctly transmitted from x to y?

Input

Input consists of several cases. Every case begins with the number of friends n and the number of probabilities p_uv that are strictly positive. Follow m triplets u, v, p_uv, where u ≠ v. Finally, we have x and y. Assume 1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 5n, and that every pair of u and v appears at most once in the input. Friends are numbered between 0 and n−1.

Output

For every case, print with five digits after the decimal point the maximum probability that the message correctly reaches y from x. If it is impossible, tell so.

Hint

The expected solution is based upon a fundamental graph algorithm.