Безквитковий проїзд
Віргілій — відданий співробітник агентства таємної національної безпеки. Щодня він витрачає багато часу на поїздки на роботу в поїзді, під час яких у нього є можливість обдумати своє становище та події з життя. Будучи математиком, він зауважив, що хоча він і платить за свої поїздки, провідники рідко перевіряють його квитки. Маючи багаторічний досвід, Віргілій має досить гарне уявлення про ймовірність перевірки між кожною парою міст.
Чи може він уникнути плати за проїзд? Звісно, якщо його спіймають у поїзді без квитка, то доведеться заплатити штраф, який значно більший за вартість квитка. Але тим не менш... А може дешевше не платити за (частину) подорожі, а виплачувати штрафи, коли спіймають?
Квиток з міста A в місто B коштує певну початкову вартість s плюс певну невелику величину p за кожен кілометр по найкоротшому шляху між A і B (квиток дійсний тільки по найкоротшому шляху). Якщо вас спіймають без квитка, то слід заплатити штраф, що складається з певної константи y плюс величину p за кожен кілометр залізничної ділянки шляху, починаючи з останнього міста, в якому побував поїзд, і до наступної станції. Правила кажуть, що ви повинні вийти на наступній зупинці, якщо вас спіймають за безквитковий проїзд. Однак, будучи співробітником такого таємного агентства, Віргілій є майстром маскування: провідники ніколи не впізнають його, і він може продовжити свою подорож, наче його і не спіймали.
Допоможіть Віргілію написати комп'ютерну програму, яка, базуючись на його досвіді, знайде шлях і дасть інформацію про квитки, які слід купити для мінімізації його очікуваних щоденних витрат^1.
Розглянемо візуалізацію третього прикладу. Найкращим варіантом дістатися з 1 до 4 - це купити квиток на відрізок шляху з 1 до 2 вартістю 20 (10 + 1 × 10), потім проїхати зайцем з 2 до 3 з очікуваною вартістю 22 (0.1 × (100 + 1 × 120)), і нарешті купити квиток на відрізок з 3 до 4 вартістю 20 (10 + 1 × 10). Загальна вартість поїздки складе 62 (20 + 22 + 20), яка є найкращою для заданої залізничної мережі.
________________________________
^1Очікувана щоденна вартість проїзду складає E[C] = P_kC_k, де P_k - ймовірність того, що вартість проїзду складає C_k, сума береться по всіх можливих вартостях. Очікувані значення адитивні, тобто E[X+Y] = E[X] + E[Y].
Вхідні дані
Перший рядок містить кількість тестів, не більше 100. Кожен тест складається з:
одного рядка з сімома цілими числами:
n (2 ≤ n ≤ 200): кількість міст у залізничній мережі;
m (1 ≤ m ≤ n(n-1)/2): кількість прямих сполучень у залізничній мережі;
start (1 ≤ start ≤ n): номер міста, в якому живе Віргілій;
end (1 ≤ end ≤ n, start ≠ end): номер міста, де працює Віргілій;
s (1 ≤ s ≤ 1000): початкова вартість квитка;
p (1 ≤ p ≤ 1000): вартість за кілометр квитка або штрафу;
y (s < y ≤ 1000): константна частина штрафу.
m рядків з чотирма цілими числами, що задають двонаправлені дороги між містами. i-ий рядок містить:
a_i (1 ≤ a_i ≤ n): індекс міста з одного боку секції i;
b_i (a_i < b_i ≤ n): індекс міста з іншого боку секції i;
c_i (0 ≤ c_i ≤ 100): ймовірність того, що кондуктор перевірить ваш квиток на секції i, виражена у відсотках;
d_i (1 ≤ d_i ≤ 1000): довжина секції i між містами a_i та b_i в кілометрах;
Для будь-якої пари (a_i, b_i) і (a_j, b_j) де i ≠ j, маємо (a_i, b_i) ≠ (a_j, b_j).
Вихідні дані
Для кожного тесту вивести в окремому рядку очікувану вартість поїздки між стартовим і кінцевим містом з двома десятковими знаками.