Вергилий является верным сотрудником агентства тайной национальной безопасности. Каждый день ему приходится тратить много времени на поездки на работу в поезде, в течение которых у него имеется возможность обдумать свое положение и события из жизни. Будучи математиком, он замечает, что хотя он и платит за свои поездки в обязательном порядке, проводники тем не менее редко проверяют его билеты. Имея многолетний опыт, Вергилий имеет достаточно хорошее представление о шансах быть проверенным между каждой парой городов. Может он сможет увернуться от платы за проезд? Конечно, если его словят в поезде без билета, то придется заплатить штраф, который значительно больше стоимости билета. Но тем не менее... А может дешевле не платить за (часть) путешествие, а выплачивать штрафы когда поймают? Билет с города \textbf{A }в город \textbf{B }обходится в некоторую начальную стоимость \textbf{s} плюс некоторую небольшую величину \textbf{p} за каждый километр по кратчайшему пути между \textbf{A }и \textbf{B }(билет действителен только по кратчайшему пути). Если Вы пойманы без билета, то следует заплатить штраф, состоящий из некоторой константы \textbf{y} плюс величину \textbf{p} за каждый километр железнодорожного участка пути начиная с последнего города, в котором побывал поезд, и до следующей станции. Правила гласят, что Вы должны выйти на следующей остановке, если вас поймают за безбилетный проезд. Однако будучи сотрудником такого тайного агентства, Вергилий является мастером маскировки: проводники никогда не узнают его, и он может продолжить свое путешествие, как будто он и не был пойман. Помогите Виргилию написать компьютерную программу, которая базируясь на его опыте найдет путь и даст информацию о билетах, которые следует купить для минимизации его ожидаемых ежедневных затрат^1. \includegraphics{https://static.e-olymp.com/content/5f/5f4f8ff073e274eeca356c0a7a22e4f18485d7c9.jpg} Рассмотрим визуализацию третьего примера. Лучшим вариантом добраться с \textbf{1} до \textbf{4} - это купить билет на отрезок пути с \textbf{1 }до \textbf{2 }стоимостью \textbf{20 (10 + 1 × 10)}, затем проехать зайцем с \textbf{2} до \textbf{3} с ожидаемой стоимостью \textbf{22 (0.1 × (100 + 1 × 120))}, и наконец купить билет на отрезок с \textbf{3} до \textbf{4} стоимостью \textbf{20 (10 + 1 × 10)}. Общая стоимость поездки составит \textbf{62 (20 + 22 + 20)}, которая является наилучшей для заданной железнодорожной сети. ________________________________ \includegraphics{https://static.e-olymp.com/content/40/40129ca62a8ff1c8e52069f168190a0e095eb750.jpg} \textbf{^1}Ожидаемая ежедневная стоимость проезда составляет \textbf{E\[C\] = } \textbf{P_kC_k}, где \textbf{P_k} - вероятность того, что стоимость проезда составляет \textbf{C_k}, сумма берется по всем возможным стоимостям. Ожидаемые значения аддитивны, то есть \textbf{E\[X+Y\] = E\[X\] + E\[Y\]}. \InputFile Первая строка содержит количество тестов, не более \textbf{100}. Каждый тест состоит из: \begin{itemize} \item одной строки с семью целыми числами: \begin{itemize} \item \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{200}): количество городов в железнодорожной сети; \item \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{n(n-1)/2)}: количество прямых соединений в железнодорожной сети; \item \textbf{start} (\textbf{1} ≤ \textbf{start} ≤ \textbf{n}): номер города, в котором живет Виргилий; \item \textbf{end} (\textbf{1} ≤ \textbf{end} ≤ \textbf{n}, \textbf{start} ≠ \textbf{end}): номер города, где работает Виргилий; \item \textbf{s} (\textbf{1} ≤ \textbf{s} ≤ \textbf{1000}): начальная стоимость билета; \item \textbf{p} (\textbf{1} ≤ \textbf{p} ≤ \textbf{1000}): стоимость за километр билета или штрафа; \item \textbf{y} (\textbf{s} < \textbf{y} ≤ \textbf{1000}): константная часть штрафа. \end{itemize} \item \textbf{m} строк с четырьмя целыми числами, задающих двунаправленные дороги между городами. \textbf{i}-ая строка содержит: \begin{itemize} \item \textbf{a_i} (\textbf{1} ≤ \textbf{a_i} ≤ \textbf{n}): индекс города с одной стороны секции \textbf{i}; \item \textbf{b_i} (\textbf{a_i} < \textbf{b_i} ≤ \textbf{n}): индекс города с другой стороны секции \textbf{i}; \item \textbf{c_i} (\textbf{0} ≤ \textbf{c_i} ≤ \textbf{100}): вероятность того, что кондуктор проверит Ваш билет на секции \textbf{i}, выражаемый в процентах; \item \textbf{d_i} (\textbf{1} ≤ \textbf{d_i} ≤ \textbf{1000}): длина секции \textbf{i} между городами \textbf{a_i} и \textbf{b_i} в километрах; \end{itemize} \end{itemize} Для любой пары \textbf{(a_i, b_i)} и \textbf{(a_j, b_j)} где \textbf{i} ≠ \textbf{j}, имеем \textbf{(a_i, b_i)} ≠ \textbf{(a_j, b_j)}. \OutputFile Для каждого теста вывести в отдельной строке ожидаемую стоимость поездки между стартовым и конечным городом с двумя десятичными знаками.