Начало нового пути
Настал день, дамы и господа! Мы отправляемся за невестой! Однако, как всегда, нас ждут узкие улицы Баку, где дети перекрывают дорогу, традиционно прося немного денег. Бедный Рашад не располагает большими средствами, чтобы раздавать их детям! Он также хочет, чтобы с ним поехало как можно больше машин. После долгих раздумий он решил выбрать маршрут с максимальной эффективностью. Эффективность маршрута определяется как максимальное количество машин, которые он может взять, делённое на общую сумму, которую он должен отдать детям (эффективность = количество_машин / общая_стоимость). В начале пути количество машин, которые Рашад может взять, равно минимальной ширине всех дорог на маршруте. Вам даны доступные дороги Баку, каждая из которых имеет свою ширину и стоимость и соединяет два местоположения. Ваша задача — найти маршрут с максимальной эффективностью от местоположения 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...