Rush Hour

The office sits at point 1 of Seoul. Seoul is split into N points numbered 1 to N. M roads connect two different points each, and every point can be reached from every other point. Each road has a length, and on a road that is not congested, covering a distance of 1 takes 1 minute.

Every employee leaves the office at minute 0. Rush hour lasts from minute S to minute E. During that window a congested road runs at half speed, so covering a distance of 1 takes 2 minutes. Congestion is set per road and per direction of travel. Some roads stay clear even during rush hour.

Suppose rush hour runs from minute 10 to minute 20 and an employee enters a congested road of length 10 at minute 15.

• From minute 15 to minute 20, the 5 minutes cover a distance of 2.5.
• The remaining distance of 7.5 takes 7.5 minutes once rush hour is over.

So the whole road takes 12.5 minutes.

An employee never stops once moving and never travels the same road twice. Everyone takes the route that arrives as early as possible and never picks a slower way on purpose. Compute the earliest arrival time at each point starting from the office, then report the latest of those times.

The first line contains the number of points N, the number of roads M, the minute S when rush hour starts, and the minute E when it ends. (2 ≤ N ≤ 5,000, 1 ≤ M ≤ 100,000, 0 ≤ S < E ≤ 1,000,000,000)

Each of the next M lines contains the two points A and B joined by a road, the length L of the road, and the congestion flags t1 and t2. (1 ≤ A, B ≤ N, A ≠ B, 1 ≤ L ≤ 1,000,000,000, t1 and t2 are 0 or 1)

• t1 equal to 1 means the road is congested during rush hour when going from A to B.
• t2 equal to 1 means the road is congested during rush hour when going from B to A.
• A flag equal to 0 means that direction is never congested.

Several roads may join the same pair of points.

Print on the first line the arrival time of the point that is reached last when starting from the office.

The answer is always a multiple of 0.5. Print it without a decimal point when it is an integer, and with exactly one digit after the decimal point otherwise.

The road network of the first example looks like this. The pink segments are the directions that get congested during rush hour.

Without rush hour the last point reached is point 7 at minute 15. The route to point 3 is congested, so point 3 becomes the last one at minute 16.

• First road: a distance of 5 takes 5 minutes, then rush hour starts and the remaining distance of 3 takes 6 minutes, so 11 minutes in total.
• Second road: a distance of 1 takes 2 minutes, then rush hour ends and the remaining distance of 3 takes 3 minutes, so 5 minutes in total.

That adds up to 16 minutes.