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