Safe Escort

Little Tim has finally escaped from the amusement park—but now the park staff are on his trail again! Your task is to safely escort him home through City A, whose complicated traffic conditions pose a serious challenge.

City A has n intersections and m one‐way roads. However, each road is only open during a specific time interval. To ensure safety, you must choose an escort route that minimizes the journey duration, defined as the difference between the arrival time at home and the departure time from the amusement park.

More formally, every road is represented by four integers u, v, l and r, indicating that a one‐way road runs from intersection u to intersection v and is available in the time interval \( [l, r] \). You start at intersection 1 (the amusement park) at time 0 and your home is located at intersection n. You can only use a road if you reach its starting intersection no later than time l; when taking a road you depart exactly at time l and arrive at time r.

The journey duration of a route is defined as \( r_{last} - l_{first} \), where \( l_{first} \) is the departure time on the first road of the route and \( r_{last} \) is the arrival time at home via the final road. If no valid route exists, output -1.

inputFormat

The first line contains two integers n and m, where 2 ≤ n and m ≥ 1.

Each of the following m lines contains four integers u, v, l and r (with \( r > l \)). This indicates a one-way road from intersection u to intersection v that is available during the time interval \( [l, r] \).

It is guaranteed that you start at intersection 1 (amusement park) at time 0 and your destination is intersection n.

outputFormat

Output a single integer representing the minimum journey duration \( (r_{last} - l_{first}) \) needed to safely escort Little Tim home. If there is no valid route from intersection 1 to intersection n, output -1.

sample

4 5
1 2 1 4
1 3 2 6
2 3 5 7
2 4 8 10
3 4 7 8

6