Virgil is a loyal employee at a mysterious national security agency. He has a long commute to work by train every day, during which his mind is free to ponder his situation and the facts of life. Always the mathematician, he notices that, although he pays the fares for his journeys without fail, the conductors rarely check his tickets. In fact, through his years of experience he has a pretty good idea of what the chances are of being checked per section between each pair of cities. Maybe he could just dodge the fares? Of course, if he gets caught in the train without a ticket he has to pay a fine that will be much higher than the cost of a ticket would have been. But still... Perhaps it’s cheaper to not pay for (part of) the journey and pay the fines if and when he does get caught. A ticket from city \textbf{A }to city \textbf{B }costs a certain start up cost \textbf{s}, plus a small amount \textbf{p} per kilometer on a shortest route between city \textbf{A }and \textbf{B }(the ticket is only valid on a shortest route). If you get caught without a ticket, you have to pay a fine consisting of a constant \textbf{y} plus the small amount \textbf{p} per kilometer on the section of railway from the last city the train visited to the next city. The regulations dictate that you have to get off at the next stop if you get caught fare dodging, but being an employee of such a mysterious agency, Virgil is a master of disguise: the conductors will never recognise him and he can continue his journey as if he was never busted. Help Virgil write a computer program that -- based on his experience -- calculates the route and which tickets to buy so that his expected daily costs^1 are as small as possible. \includegraphics{https://static.e-olymp.com/content/5f/5f4f8ff073e274eeca356c0a7a22e4f18485d7c9.jpg} A visual representation of the third sample. The best route from \textbf{1} to \textbf{4} is to buy a ticket for section \textbf{1 }to \textbf{2 }for a cost of \textbf{20 (10 + 1 × 10)}, then dodge the fares for section \textbf{2} to \textbf{3} for an expected cost of \textbf{22 (0.1 × (100 + 1 × 120))}, and finally buy a ticket for section \textbf{3} to \textbf{4} for a cost of \textbf{20 (10 + 1 × 10)}. This leads to a total expected cost of \textbf{62 (20 + 22 + 20)} which is the best possible for this rail network. ________________________________ \includegraphics{https://static.e-olymp.com/content/40/40129ca62a8ff1c8e52069f168190a0e095eb750.jpg} \textbf{^1}The expected daily costs can be calculated as \textbf{E\[C\] = } \textbf{P_kC_k}, where \textbf{P_k} is the probability that the costs are \textbf{C_k}, and the sum is over all possible costs. Expectation values are additive, i.e. \textbf{E\[X+Y\] = E\[X\] + E\[Y\]}. \InputFile On the first line one positive number: the number of test cases, at most \textbf{100}. After that per test case: \begin{itemize} \item one line with seven space-separated integers: \begin{itemize} \item \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{200}): the number of cities in the rail network; \item \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{n(n-1)/2)}: the number of direct connections in the rail network; \item \textbf{start} (\textbf{1} ≤ \textbf{start} ≤ \textbf{n}): the index of the city that Virgil lives in; \item \textbf{end} (\textbf{1} ≤ \textbf{end} ≤ \textbf{n}, \textbf{start} ≠ \textbf{end}): the index of the city that Virgil works at; \item \textbf{s} (\textbf{1} ≤ \textbf{s} ≤ \textbf{1000}): the start up cost of a ticket; \item \textbf{p} (\textbf{1} ≤ \textbf{p} ≤ \textbf{1000}): the cost per kilometer of a ticket or fine; \item \textbf{y} (\textbf{s} < \textbf{y} ≤ \textbf{1000}): the constant part of a fine. \end{itemize} \item \textbf{m} lines with four space-separated integers, describing the bidirectional sections between cities, with on line \textbf{i}: \begin{itemize} \item \textbf{a_i} (\textbf{1} ≤ \textbf{a_i} ≤ \textbf{n}): the index of one city on the end of section \textbf{i}; \item \textbf{b_i} (\textbf{a_i} < \textbf{b_i} ≤ \textbf{n}): the index of the other city of section \textbf{i}; \item \textbf{c_i} (\textbf{0} ≤ \textbf{c_i} ≤ \textbf{100}): the probability that a conductor will check your ticket on section \textbf{i}, expressed as a percentage; \item \textbf{d_i} (\textbf{1} ≤ \textbf{d_i} ≤ \textbf{1000}): the distance traveled along section \textbf{i} between city \textbf{a_i} and \textbf{b_i} in kilometers; \end{itemize} \end{itemize} For any two pairs \textbf{(a_i, b_i)} and \textbf{(a_j, b_j)} with \textbf{i} ≠ \textbf{j}, we have that \textbf{(a_i, b_i)} ≠ \textbf{(a_j, b_j)}. \OutputFile Per test case print the lowest possible expected costs for a single trip between city start and end, rounded to exactly two decimals.