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.
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.
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 the shortest value in the total time of two downhills in one line.
3 3 1 2 1 2 2 3 1 2 1 3 1 3
3
3 3 1 2 1 2 2 3 1 2 1 3 1 1
2
4 5 1 2 3 5 1 3 1 3 3 2 2 5 2 4 6 1 3 4 5 5
13