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