C. Brunch Commute
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Beth want to meet up for brunch. They both live in different parts of the city; Alice drives and Beth rides a bike. Given a map of the city and the amount of time it takes Alice and Beth to travel along each road, what's the soonest they can meet up, if both leave their apartments immediately?

More specifically, if $$$P$$$ is an intersection in the city, then the time it takes Alice and Beth to meet up at $$$P$$$ is the maximum of Alice and Beth's travel time to $$$P$$$. Find the $$$P$$$ that minimizes this maximum travel time and print that travel time.

There are brunch places all over the city, but only near the intersections: not in the middle of random roads. So Alice and Beth are only interested in meeting up at a city intersection.

Input

The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 1\,000$$$; $$$1 \leq M \leq 50\,000$$$), the number of intersections and roads in the city, respectively.

The next $$$M$$$ lines describe the roads. Each line contains four space-separated integers $$$u$$$, $$$v$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq u \lt v \leq N$$$; $$$0 \leq a, b \leq 100$$$) indicating that there is a road connecting intersections $$$u$$$ and $$$v$$$, and that it takes Alice and Beth $$$a$$$ and $$$b$$$ minutes to travel along that road, respectively.

Roads can be traveled in either direction. There is at most one road between any pair of intersections.

Alice lives at intersection $$$1$$$ and Beth lives at intersection $$$N$$$.

Output

Print the shortest amount of time it takes for Alice and Beth to meet up at a common intersection, if both leave their apartments at the same time and travel as quickly as possible towards the intersection that minimizes this time.

If it's impossible for Alice and Beth to meet up anywhere in the city, print $$$-1$$$ instead.

Example
Input
6 7
1 2 10 35
2 3 1 4
2 4 5 15
2 5 2 3
3 6 11 20
4 6 5 2
5 6 0 1
Output
10