Happy Birthday#2852
The long-awaited birthday has come. Only one test remains: to reach Ira's home.
The most popular form of transportation in the city is the minibus. Each minibus has two drivers: one prefers one route, and the other prefers another. However, the starting place and departure time for both drivers are the same. Each day, one of the drivers works and the other rests. If Sasha is at any bus stop, he immediately learns which drivers are working today for the minibuses departing from that stop. However, before reaching a stop, he only knows the possible movement schedule of minibuses and the probability that the first driver is working today. Sasha lives near stop 1 and can be there at any time, while Ira lives near stop N. You need to find the expected time of arrival to Ira on Sasha's birthday. Sasha will never use a route that could result in not reaching Ira at all, and among all other possible routes, he chooses one that minimizes the expected time of arrival.
Important facts:
The minibus network is an acyclic directed graph.
Transfers between minibuses are instantaneous.
In determining the optimal strategy, Sasha takes into account that upon arriving at each stop, he will learn which drivers are working today.
Initially, Sasha does not know the drivers on his starting stop either.
The first line contains two integers and (2 \leq N \leq 10^5, 0 \leq K \leq 10^5) — the number of stops and active minibuses. Each of the next lines contains information about a minibus: seven integers v_1 a_1 v_2 a_2 (1 \leq u, v_1, v_2 \leq N, u \neq v_1, u \neq v_2, 0 \leq d, a_1, a_2 \leq 1440, d < a_1, d < a_2, 0 < p < 100) — the stop number and departure time, the probability that the first driver works, and for each driver: the destination stop and time of arrival.
Output a single number — the expected arrival time at stop with an absolute or relative error of 10^{-6}, or if there is a nonzero probability of not reaching there at all.
Example 1