Bancopia

Gold transports in Bancopia are risky because of frequent robberies, and some roads are more dangerous than others. To move gold safely between two cities, the Bancopians want to place police posts on some roads to make them safer.

You are given the cities of Bancopia, the roads between them, and the two cities the gold transport travels between. Each road has a robbery probability: given that a gold transport uses that road, this is the probability that a robbery happens on that road. Robberies on different roads are independent.

You are also given the maximum number of police posts you may place. At most one police post can be placed on each road, and a police post exactly halves the robbery probability of that road.

The transport always takes the safest route between the two cities: the route with the smallest overall robbery probability. If a route uses roads with (possibly halved) robbery probabilities $p_1, p_2, \dots, p_k$, its overall robbery probability is $1 - \prod_{i=1}^{k}(1 - p_i)$.

Place the police posts so that the robbery probability of the safest route is as small as possible, and report that minimum probability.

The first line contains a single integer $T$: the number of test cases. Each test case has the following format:

• One line with five integers $n$, $w$, $m$, $a$, $b$ separated by spaces, where $2 \le n \le 100$ is the number of cities, $1 \le w \le 10^4$ is the number of roads, $1 \le m \le 100$ is the maximum number of police posts, and $a$ and $b$ are the two cities between which the transport travels. Cities are numbered with distinct integers from ${1, \dots, n}$.
• $w$ lines, each describing one road with three values $s_1$, $s_2$, $p$ separated by spaces, where $s_1$ and $s_2$ are the cities the road connects ($s_1 \ne s_2$, $1 \le s_1, s_2 \le n$) and $0 \le p \le 1$ is the robbery probability of that road.

No two roads connect the same pair of cities. Every road is bidirectional, and its robbery probability is the same in both directions. It is guaranteed that at least one route from $a$ to $b$ exists.

For each test case, print a single line containing one number: the robbery probability of the safest route from $a$ to $b$ when at most $m$ police posts are placed to minimize this probability, rounded to four digits after the decimal point. Rounding is done the usual way (round half up): $0.12345\ldots$ becomes $0.1235$ and $0.12344\ldots$ becomes $0.1234$.

Figure 1: The maps illustrate one scenario. The left map shows the safest route without police posts; the right map shows the safest route after the posts are placed. Cities are numbered and each road is labelled with its robbery probability. Next to the destination city, the robbery probability of the entire route is shown.