Настал долгожданный день рожденья. Осталось только одно испытание --- добраться к Ире домой. Самый популярный вид транспорта в городе --- маршрутки. У каждой маршрутки есть два водителя, один из них любит один маршрут, а второй --- другой. Правда место и время отправления маршрутки одинаковы для обоих водителей. Каждый день один из водителей работает, а второй отдыхает. Если Саша окажется на какой-то остановке, то он сразу же узнает, какие из водителей работают сегодня на маршрутках, отправляющихся с этой остановки. Однако до того, как он попадет на остановку, он знает только расписание возможного движения маршруток и вероятность того, что работает первый водитель. Саша живет возле остановки с номером \textbf{1} и может оказаться на ней в любое время, а Ира живет рядом с остановкой \textbf{N}. Требуется найти математическое ожидание времени прибытия к Ире на день рожденья. При этом Саша никогда не воспользуется способом, который может привести к тому, что он не попадет к Ире вообще, а среди всех остальных выбирает тот, который минимизирует ожидаемое время прибытия. Важные факты: \begin{itemize} \item Сеть движения маршруток представляет собой ациклический ориентированный граф. \item С маршрутки на маршрутку можно пересаживаться мгновенно. \item При определении оптимальной стратегии Саша использует в том числе и то, что по прибытии на каждую остановку он узнает сегодняшних шоферов. \item О своей остановке Саша тоже изначально ничего не знает. \end{itemize} \InputFile В первой строке даны два числа \textbf{N} и \textbf{K} (\textbf{2} ≤ \textbf{N} ≤ \textbf{10^5}, \textbf{0} ≤ \textbf{K} ≤ \textbf{10^5}) --- число остановок и действующих маршруток. Далее в каждой из \textbf{K} строк описана информация о маршруках: семь целых чисел \textbf{u d p v_1 a_1 v_2 a_2} (\textbf{1} ≤ \textbf{u}, \textbf{v_1}, \textbf{v_2} ≤ \textbf{N}, \textbf{u} ≠ \textbf{v_1}, \textbf{u} ≠ \textbf{v_2}, \textbf{0} ≤ \textbf{d}, \textbf{a_1}, \textbf{a_2} ≤ \textbf{1440}, \textbf{d} < \textbf{a_1}, \textbf{d} < \textbf{a_2}, \textbf{0} < \textbf{p} < \textbf{100}) --- номер остановки и время отправления, вероятность того, что работает первый водитель, место и время прибытия, если работает первый водитель, место и время прибытия, если работает второй водитель. \OutputFile Единственное число --- математическое ожидание времени прибытия на остановку \textbf{N} с абсолютной или относительной погрешностью \textbf{10^\{-6\}} или \textbf{-1}, если есть ненулевая вероятность туда не попасть.