Резервування Маршруту
Місто складається виключно з односторонніх вулиць. Кожна вулиця в місті має пропускну здатність, яка визначається мінімальною пропускною здатністю вулиць уздовж цього маршруту.
Коефіцієнт надлишковості від точки A до точки B — це відношення максимальної кількості автомобілів, які можуть дістатися від точки A до точки B за годину, використовуючи всі маршрути одночасно, до максимальної кількості автомобілів, які можуть дістатися від точки A до точки B за годину, використовуючи один маршрут. Мінімальний коефіцієнт надлишковості — це число, що дорівнює пропускній здатності одного маршруту з найбільшою пропускною здатністю.
Вхідні дані
Перша строка введення містить одне ціле число P (1 ≤ P ≤ 1000), яке є кількістю наборів даних, що слідують. Кожен набір даних складається з кількох рядків і представляє орієнтований граф з додатними цілими вагами.
Перша строка кожного набору даних містить п'ять цілих чисел, розділених пробілами. Перше число D — це номер набору даних. Друге число N (2≤N≤1000) — це кількість вузлів у графі. Третє число E (E ≥ 1) — це кількість ребер у графі. Четверте число A (0 ≤ A < N) — це індекс точки A. П'яте число B (0 ≤ B < N, A ≠ B) — це індекс точки B.
Наступні E рядків описують кожне ребро. Кожен рядок містить три цілі числа, розділені пробілами. Перше число U (0 ≤ U < N) — це індекс вузла U. Друге число V (0 ≤ V < N, V ≠ U) — це вузол V. Третє число W (1 ≤ W ≤ 1000) — це пропускна здатність (вага) шляху від U до V.
Вихідні дані
Для кожного набору даних виводиться один рядок. Він містить номер набору даних (N), за яким слідує один пробіл, а потім значення з плаваючою комою, яке є мінімальним коефіцієнтом надлишковості з точністю до 3 знаків після коми.