Happy Birthday#2852
Довгоочікуваний день народження нарешті настав. Залишилося лише одне випробування: дістатися додому до Іри.
Найпопулярніший вид транспорту у місті — маршрутка. У кожної маршрутки два водії: один віддає перевагу одному маршруту, а інший — іншому. Проте місце відправлення та час відправлення у обох водіїв однакові. Щодня працює хтось один із водіїв, а інший відпочиває. Якщо Саша перебуває на будь-якій зупинці, він миттєво дізнається, які водії сьогодні працюють на маршрутках, що відправляються з цієї зупинки. Проте до прибуття на зупинку він знає лише можливий розклад руху маршруток та ймовірність того, що сьогодні працює перший водій. Саша живе біля зупинки 1 та може опинитися там у будь-який момент часу, а Іра мешкає біля зупинки N. Необхідно знайти очікуваний час прибуття до Іри на день народження Саші. Саша ніколи не обиратиме маршрут, який може призвести до того, що він взагалі не дістанеться до Іри, і серед усіх інших можливих маршрутів обирає той, що мінімізує очікуваний час прибуття.
Важливі факти:
Мережа маршруток є ациклічним орієнтованим графом.
Пересадки між маршрутками відбуваються миттєво.
Визначаючи оптимальну стратегію, Саша враховує, що на кожній зупинці він дізнається, які водії працюють сьогодні.
Спочатку Саша також не знає, які водії працюють на його початковій зупинці.
Перший рядок містить два цілих числа і (2 \leq N \leq 10^5, 0 \leq K \leq 10^5) — кількість зупинок та число активних маршруток. Кожен із наступних рядків містить інформацію про маршрутку: сім цілих чисел v_1 a_1 v_2 a_2 (1 \leq u, v_1, v_2 \leq N, u \neq v_1, u \neq v_2, 0 \leq d, a_1, a_2 \leq 1440, d < a_1, d < a_2, 0 < p < 100) — номер зупинки та час відправлення, ймовірність того, що працює перший водій, а також для кожного водія: зупинка призначення та час прибуття.
Виведіть одне число — очікуваний час прибуття на зупинку з абсолютною або відносною похибкою 10^{-6}, або , якщо існує ненульова ймовірність того, що дістатися туди взагалі неможливо.
Приклад 1