Synchronized Field Travel

Bessie and her sister Elsie want to travel from the barn to their favorite field such that they leave at exactly the same moment from the barn and arrive at exactly the same moment at their favorite field.

The farm is represented by N fields, numbered from 1 to N. Field 1 contains the barn and field N is the favorite field. The fields are arranged by elevation so that field X is higher than field Y if and only if X < Y. There are M directed paths (with M ≤ N(N-1)/2) connecting pairs of fields. Each path is very steep and can only be traversed downhill (i.e. from a lower‐numbered field to a higher‐numbered field).

For each path from field u to field v, Bessie takes time t_B and Elsie takes time t_E to travel. Both cows travel instantly through the fields (they do not wait in any field). They must select routes (which may be different) from field 1 to field N so that the total travel times for both become equal, and they want to minimize this common arrival time.

If we denote by \( T_B \) the total time Bessie takes and \( T_E \) the total time Elsie takes, you need to find the minimum common time \( T \) such that:

[ T = T_B = T_E ]

If no such pair of routes exist, output -1.

inputFormat

The first line contains two integers N and M (1 ≤ N ≤ 100, M ≤ N(N-1)/2), representing the number of fields and the number of paths, respectively.

Each of the next M lines contains four integers u v t_B t_E. This indicates there is a downhill path from field u to field v (with u < v) requiring time t_B for Bessie and time t_E for Elsie.

outputFormat

Output a single integer, which is the minimum time needed for Bessie and Elsie to travel from field 1 to field N such that they both arrive at the same time. If it is impossible, output -1.

sample

4 6
1 2 3 4
1 3 4 3
2 3 2 1
2 4 5 3
3 4 1 1
1 4 10 5

5