Настав довгоочікуваний день народження. Залишилось лише одне випробування --- дістатись до Іри додому. Найпопулярніший вид транспорту у місті --- маршрутки. У кожної маршрутки є два водія, один з них полюбляє один маршрут, а другий --- інший. Правда місце і час відправлення маршрутки однакові для обох водіїв. Кожен день один з водіїв працює, а інший відпочиває. Якщо Саша опиниться на якійсь зупинці, то він відразу ж взнає, які з водіїв працюють сьогодні на маршрутках, що відправляються з цієї зупинки. Проте до того, як він потрапить на зупинку, він знає лише розклад можливого руху маршруток і ймовірність того, що працює перший водій. Саша живе біля зупинки з номером \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}, якщо існує ненульова ймовірність туди не потрапити.