Pedestrian and Cyclist
Two teammates were engrossed in a conversation about life and completely lost track of time. Suddenly, they realized they were late for the quarter-finals of the World Programming Championship, and they were on the opposite side of the city. Fortunately, one of them had a bicycle. However, according to the competition rules, the team cannot compete until all members are present. Therefore, it is crucial to determine when the last team member arrives. If one of them uses the bicycle to reach the venue, the other will have to walk the entire distance. Both are equally skilled at cycling, so they ride at the same speed. Unfortunately, they do not know how to ride the bicycle together.
The teammates quickly devised a plan to reach the competition venue. The plan involves N intersections and M roads connecting them. They chose a single direction for each road, meaning once they leave an intersection, they cannot return to it. They realized that after cycling a certain distance, they could leave the bicycle for the other person, who is walking, to use.
By doing this, they can minimize their travel time. Your task is to help the teammates find out the minimum time they can reach the destination, considering that the bicycle can only be left at designated parking spots available at each intersection. (Otherwise, they risk losing the bicycle).
Input
The first line of the input contains two numbers N and M (N ≤ 150; 1 ≤ M ≤ N(N-1)/2). The next M lines each contain 4 natural numbers - a description of the road: u, v, b, p. This indicates there is a road from intersection u to intersection v, which can be traveled by bicycle in b minutes and on foot in p minutes. It is always faster to travel by bicycle, i.e., 1 ≤ b ≤ p ≤ 30.
When cycling, the speed depends on the road quality.
The teammates start at intersection 1 and aim to reach intersection N.
Output
Output a single number - the minimum time in minutes needed to reach the destination.