Pedestrian and Cyclist#1754
Two teammates were engaged in a conversation and lost track of time. Suddenly, they realized they were late for the quarter-finals of the World Programming Championship and were at the other end of the city. Luckily, one of them had a bicycle. However, according to the competition rules, the team is not allowed to compete until all members are present, so it is important when the last teammate arrives. If one of them takes the bicycle and reaches the finish, the other will have to walk the entire distance. Both are equally skilled at cycling, so they move at the same speed, but unfortunately, they cannot ride the bicycle together.
The teammates quickly created a route to reach the competition venue. The route consists of intersections and one-way roads connecting them. Once an intersection is left, they cannot return to it. The friends quickly realized that after traveling a certain distance, the cyclist can leave the bicycle at a special parking spot for the other, who is walking, to pick up and continue. In this way, they can reduce the total travel time. Your task is to help the teammates find out the minimum time needed to reach the destination, given that the bicycle may be left only at designated bicycle parking areas present at each intersection (otherwise, they risk losing the bicycle).
The first line contains two numbers and (N \leq 150, 1 \leq M \leq \frac{N (N - 1)}{2}). Each of the next lines describes a road and contains four natural numbers: , , , . This means there is a road from intersection to intersection . It can be traversed by bicycle in minutes, and on foot in minutes. It is always faster to use the bicycle, that is, 1 \leq b \leq p \leq 30.
When moving by bicycle, the speed depends on the quality of the road.
The two teammates start at intersection and want to reach intersection .
Print a single number — the minimum time in minutes required to reach the destination.
Example 1