Fare Dodging

Sanghyun is an agent of a secret organization, and he takes a train to work every morning. One day he noticed something unfair. He pays the fare every single day, yet a conductor almost never checks his ticket. Over several years he wrote down, for every track, how likely a check is on the train that runs it.

The fine for fare dodging is usually larger than the fare itself. Instead of skipping the fare everywhere, Sanghyun works out the fares, the fines and the check probabilities, then commutes the way that makes the expected cost as small as possible. On some legs buying a ticket is better, on others riding for free is better.

A ticket is bought for a source A and a destination B. It costs the base fare $s$ won plus $p$ won per kilometer of the shortest distance between A and B, that is $s + p \times \mathrm{dist}(A, B)$ won, where $\mathrm{dist}(A, B)$ is the shortest distance between the two cities. The ticket is valid only on trains that run the shortest route between A and B.

If a check happens on a train Sanghyun boarded without a ticket, he pays a fine. The fine is a base of $y$ won plus $p$ won per kilometer of the distance from the city the train visited last to the stop it is pulling into. A fare dodger normally has to leave the train at once, but Sanghyun is a secret agent and good at disguises. He pays the fine and stays on board.

Write a program that finds the commute from start to end with the smallest expected cost and reports that expected cost.

The first line has the number of test cases $T$. ($T \le 100$)

Each test case is laid out as follows.

• The first line has 7 integers separated by spaces.

  1. $n$ ($2 \le n \le 200$): the number of cities on the train network
  2. $m$ ($1 \le m \le n(n-1)/2$): the number of tracks that directly join two cities
  3. $\mathrm{start}$ ($1 \le \mathrm{start} \le n$): the source
  4. $\mathrm{end}$ ($1 \le \mathrm{end} \le n$, $\mathrm{start} \ne \mathrm{end}$): the destination
  5. $s$ ($1 \le s \le 1000$): the base fare of a ticket
  6. $p$ ($1 \le p \le 1000$): the per kilometer amount added to a ticket and to a fine
  7. $y$ ($s < y \le 1000$): the base fine for fare dodging

• Each of the next $m$ lines describes one track with 4 integers separated by spaces. Every track is bidirectional. Line $i$ holds the following.

  1. $a_i$ ($1 \le a_i \le n$): the city at one end of track $i$
  2. $b_i$ ($a_i < b_i \le n$): the city at the other end of track $i$
  3. $c_i$ ($0 \le c_i \le 100$): the probability that a ticket is checked on the train running track $i$, given as a percentage
  4. $d_i$ ($1 \le d_i \le 1000$): the length of track $i$ in kilometers

For every pair with $i \ne j$, $(a_i, b_i) \ne (a_j, b_j)$, so the same two cities are never joined twice. A route from start to end always exists.

For each test case print, on its own line, the smallest expected cost of getting from start to end. Print two digits after the decimal point, and keep both digits even when they are zeros.

Every fare and every expected fine lands exactly on a multiple of 0.01 won, so no rounding is ever ambiguous.

The expected fine is the check probability times the fine. Checks on different tracks are independent, so if the expected cost on route X is $E[X]$ and the expected cost on route Y is $E[Y]$, then the expected cost of X followed by Y is $E[X] + E[Y]$.

In the third case of the public test, the best route from city 1 to city 4 is this. From city 1 to city 2 buy a ticket for 20 won ($10 + 1 \times 10$), from city 2 to city 3 ride for free (the expected fine there is $0.1 \times (100 + 1 \times 120) = 22$ won), and from city 3 to city 4 buy another ticket for 20 won ($10 + 1 \times 10$). That commute has an expected cost of $20 + 22 + 20 = 62$ won, and nothing beats it.