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 \ne v$. Finally, we have $x$ and $y$. Assume $1 \le n \le 10^4$, $0 \le m \le 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.