Перекачування молока
Фермер Джон нещодавно придбав нову ферму, щоб розширити свою молочну імперію. Ця ферма з'єднана з сусіднім містом мережею труб, і Джон хоче визначити найкращий набір труб для перекачування молока з ферми до міста.
Мережа трубопроводів складається з n точок з'єднання (кінцевих точок труб), пронумерованих від 1 до n. Точка з'єднання 1 є фермою Джона, а точка з'єднання n — містом. Існує m двонаправлених труб, кожна з яких з'єднує дві точки з'єднання. i-та труба коштує c[i] доларів, і Джон може її придбати для використання, причому вона підтримує швидкість потоку f[i] літрів молока в секунду.
Джон прагне придбати труби для одного маршруту, що з'єднує точки 1 і n. Вартість маршруту — це сума вартостей труб уздовж нього. Швидкість потоку на маршруті визначається мінімальною пропускною здатністю труб на цьому маршруті (оскільки вона є вузьким місцем для потоку). Джон хоче максимізувати відношення пропускної здатності до вартості маршруту. Гарантується, що існує принаймні один шлях від 1 до n.
Вхідні дані
Перший рядок містить числа n (2 ≤ n ≤ 1000) і m (1 ≤ m ≤ 1000). Кожен з наступних m рядків описує трубу чотирма цілими числами: a і b (два різних з'єднання, з'єднаних трубою), c (вартість) і е (пропускна здатність). Вартість і пропускна здатність є натуральними числами в діапазоні від 1 до 1000.
Вихідні дані
Виведіть оптимальну відповідь, помножену на 10^6, усічену до цілого числа (тобто округлену до найближчого меншого цілого числа, якщо це число саме не є цілим).
Приклад
У прикладі є лише один шлях від 1 до n. Його пропускна здатність дорівнює min(3, 4) = 3, а вартість дорівнює 2 + 5 = 7.