Downhill Race

You are participating in a ski competition held at Mt. Bandai. In this competition, each skier will ski down the slope twice and compete for the shortest total time. There are a number of flags on the slope, and a line is set up between them for the competitors to follow. Competitors follow the lines from the start point to the finish point. The lines are set up as follows.

• One or more lines extend from a flag except at the finish point.
• There is only one line at most that directly connects one flag to another.
• The line can only be slid down in a certain direction.
• You can always reach any flag from the start, and you can reach the goal from any flag.
• No matter how you follow the line, you will never return to the same flag.

The athlete can decide which flag to go to next by choosing a line that extends from the flag they are currently on. The choice of line is free, so players can follow a different line to the finish point for each descent.

The night before the competition, Mr. Salt, the sports doctor, predicted the condition of the slope when you skied. According to him, the line you took on the first descent will change the snow quality due to the passage, so if you take the same line on the second descent, the time it will take may change. Salt told you how long it takes to go through each line the first time and how long it takes to go through it the second time. You must use this information to find a way to ski the line that minimizes the total time of the two descents.

Given the conditions of the slope, write a program that calculates the shortest total time for the two descents.

Input

The input is given in the following format.

N P
s1 e1 t1,1 t1,2
s2 e2 t2,1 t2,2
:
sP eP tP,1 tP,2

On the first line, the number of flags N (2 ≤ N ≤ 1000) and the number of lines connecting the two flags P ( 1 ≤ P ≤ 2000) are given. The flags are numbered from 1 to N , the starting point flag number is 1 and the goal point flag number is N . The following P lines give information about the line connecting the two flags. Each line has the source flag number s _i (1 ≤ s _i < N ), the destination flag number e _i (1 < e _i ≤ N ) , time required for the first pass t _{i, 1} (1 ≤ t _{i, 1} ≤ 100000), the time required to pass the same line at the second time t _{i, 2} (1 ≤ t _{i, 2} ≤ 100000).

Output

Output the shortest value in the total time of two downhills in one line.

Sample Input 1

3 3
1 2 1 2
2 3 1 2
1 3 1 3

Sample Output 1

3

Sample Input 2

3 3
1 2 1 2
2 3 1 2
1 3 1 1

Sample Output 2

2

Sample Input 3

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

Sample Output 3

13

---