Happy Birthday
Then came the long-awaited birthday. Only one test left - fi nd a way to Ira's home.
The most popular form of transport in the city are buses. Each bus has two drivers, one of them knows one route, and the other - other route. However the time and place of start are the same for both bus drivers. Each day one of the drivers is working, and the other is resting. If Alex is on a bus stop, he will immediately know which drivers are now working on buses departing from this stop. However, before he reaches the stop, he only knows the schedule of possible movement of buses and the probabllity that the rst driver works today. Sasha lives near a bus stop with number 1 and can be on it at any time, and Ira lives near to the stop N. Find the average arrival time for Sasha. At the same time Sasha would never use a way that could cause not reaching Ira's home at all, but among all the other he chooses the one that minimizes the expected time of arrival.
Important facts:
Network trafi c of buses is an acyclic directed graph.
You can instantly change from one bus to another one.
In determining the optimal strategy Sasha also counts that on arrival at each stop, he gets the informations about today's drivers.
Initially, Sasha doesn't know extra information even about his stop.
Input
In the fi rst row are given two integers N and K (2 ≤ N ≤ 10^5, 0 ≤ K ≤ 10^5) — the number of stops and buses. In each of the next K lines information about buses is described: seven integers 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) — number of stops and time of departure, the probability that the rst driver works, place and time of arrival, for fi rst and for second driver, respectively.
Output
Print average arrival time to N'th stop for Sasha with an absolute or a relative error of 10^{-6}, or -1, if there is a nonzero probability of not getting there at all.