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, если есть ненулевая вероятность туда не попасть.