Shortest Travel Time

You are given a railway network with N stations and M sections. Each section is described by four integers u, v, t, s where:

• u and v denote the connected stations.
• t represents the travel time if the train moves at its maximum allowed speed on that section.
• s is the speed limit allowed on that section (this value is provided for context, but will not affect the computation).

Your task is to compute the shortest travel time required to go from station 1 to station N. If no route exists, return -1.

Constraints:

• 2 ≤ N ≤ 1,000
• 1 ≤ M ≤ 10,000
• 1 ≤ u, v ≤ N
• 1 ≤ t ≤ 10⁸
• 1 ≤ s ≤ 300

Example:

Input:
3 3
1 2 2 150
2 3 3 200
1 3 10 300
Output:
5

</p>

inputFormat

The first line of input contains two integers: N (the number of stations) and M (the number of railway sections).

Then, M lines follow; each line contains four space-separated integers: u v t s representing a railway section.

Input is provided via standard input (stdin).

outputFormat

Output a single integer on a new line: the minimum travel time from station 1 to station N. If it is impossible to reach station N, output -1.

Output should be written to standard output (stdout).

## sample

3 3
1 2 2 150
2 3 3 200
1 3 10 300

5