Початок нової подорожі
День настав, пані та панове! Ми забираємо наречену! Проте, як завжди, вузькі вулиці Баку та діти, які блокують дорогу, вимагаючи грошей, створюють перешкоди для автомобілів. Бідолаха Рашад не має багато грошей, щоб витратити на дітей! Він також хоче, щоб з ним їхало якомога більше автомобілів. Після довгих роздумів, він вирішив обрати маршрут з максимальною ефективністю. Ефективність маршруту визначається як максимальна кількість автомобілів, які він може взяти, поділена на загальну суму грошей, яку він повинен дати дітям (ефективність = кількість_автомобілів / загальна_вартість). На початку маршруту кількість автомобілів, які може взяти Рашад, дорівнює мінімальній ширині всіх доріг на маршруті. Вам надано доступні дороги Баку, кожна з яких має свою ширину та вартість і з'єднує два місця. Ваше завдання — знайти максимальну ефективність можливого маршруту від місця 1 до місця N. Дивіться формат виводу для деталей.
Вхід:
У першому рядку дано числа N (1 ≤ N ≤ 10^3) та M (1 ≤ M ≤ 10^4). Кожен з наступних M рядків містить 4 числа: перший кінець дороги, другий кінець дороги, вартість дороги x[i] (1 ≤ x[i] ≤ 10^3), та ширину дороги y[i] (1 ≤ y[i] ≤ 10^3).
Вихід:
Виведіть 1000000 разів максимальну ефективність маршруту, округлену вниз до найближчого цілого числа.
Пояснення до першого тестового випадку
У цьому прикладі є лише один маршрут від 1 до N. Ширина дорівнює min(3, 4)=3, а вартість 2+5=7. 3/7=0.428571428571..