Minimizing GPS Complaints

John recently purchased a new car and mistakenly installed two GPS systems. Unfortunately, these two systems often provide different route suggestions. John’s area has \( N \) intersections (with \( 2 \leq N \leq 100000 \)) and \( M \) one-way roads (with \( 1 \leq M \leq 500000 \)). For the \( i\)-th road, it connects intersection \( A_i \) to \( B_i \) and has two travel times: \( P_i \) (the time computed by the first GPS) and \( Q_i \) (the time computed by the second GPS), where \( 1 \leq P_i, Q_i \leq 100000 \). Note that there could be multiple roads between two intersections. A two-way road is modeled as a pair of one-way roads in opposite directions.

John's home is at intersection 1 and his farm is at intersection \( N \). He can drive along a sequence of one-way roads from his home to the farm. Both GPS systems use the same underlying map information; the only difference is how they compute the travel time on each road. For a road from intersection \( u \) to \( v \), let the travel times be \( P_{uv} \) and \( Q_{uv} \) for the two systems.

Before starting his journey, both GPS systems compute the shortest travel time from every intersection to the farm according to their own weight calculations. Specifically, for each intersection \( v \), let \( d_1(v) \) be the minimum sum of \( P \) weights from \( v \) to \( N \) and \( d_2(v) \) be the minimum sum of \( Q \) weights from \( v \) to \( N \). When John traverses a road from \( u \) to \( v \), the first GPS will complain if

[ d_1(u) \neq P_{uv} + d_1(v), ]

and the second GPS will complain if

[ d_2(u) \neq Q_{uv} + d_2(v). ]

If both systems complain for a road, that road contributes 2 to the total number of complaints. John wants to choose a path from his home (intersection 1) to the farm (intersection ( N )) that minimizes the total number of complaints he receives.

Your task is to compute the minimum number of GPS complaints that John may receive on his journey.

inputFormat

The first line contains two integers \( N \) and \( M \).

Each of the following \( M \) lines contains four integers \( A_i, B_i, P_i, Q_i \), describing a one-way road from intersection \( A_i \) to intersection \( B_i \) with travel times \( P_i \) (first GPS) and \( Q_i \) (second GPS).

outputFormat

Output a single integer, the minimum total number of GPS complaints on an optimal route from intersection 1 to intersection \( N \).

sample

4 4
1 2 1 2
2 4 1 1
1 3 2 2
3 4 1 1

0