Description

Farmer John recently bought a new car online. While ordering accessories, he accidentally clicked the “Submit” button twice, so the car was fitted with two GPS systems. Even worse, the two systems often suggest different routes during navigation. The region where John lives has $N$ ($2 \le N \le 10^5$) intersections and $M$ ($1 \le M \le 5 \times 10^5$) directed roads. The $i$-th road goes from intersection $A_i$ ($1 \le A_i \le N$) to $B_i$ ($1 \le B_i \le N$). There may be multiple roads between the same pair of intersections. A bidirectional road can be modeled as two directed roads in opposite directions.

John’s home is at intersection $1$, and the farm is at intersection $N$. John can drive from home to the farm along a sequence of directed roads. Both GPS systems share the same base map; the only difference is how they compute travel times for each road. For the $i$-th road, the first GPS estimates a travel time of $P_i$ units, and the second GPS estimates $Q_i$ units. All road travel times are integers in the range $1$ to $10^5$.

John wants to drive from home to the farm. Along the way, the GPS systems keep nagging him with prompts like “Please go from intersection $X$ to intersection $Y$.” This happens because John follows the route recommended by one GPS, while the other GPS considers this not to be a shortest path from $X$ to the farm. We call each such event a complaint from a GPS.

Please compute the minimum total number of complaints John will hear if he chooses an appropriate route to the farm. If, on some road, both GPS systems complain, then the total number of complaints increases by $2$.

Input Format

The first line contains two integers $N$ and $M$.

The next $M$ lines describe the roads. The $i$-th line contains $A_i, B_i, P_i, Q_i$.

Output Format

Output a single integer, the minimum total number of complaints along John’s route.

5 7 
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5

1

Hint

Translated by ChatGPT 5