Minimizing GPS Complaints

Farmer John mistakenly equipped his new car with two GPS systems. Unfortunately, these systems may give a complaint whenever Farmer John chooses a road which they do not believe is part of a shortest path from the current intersection to the farm. The map is given as a directed graph with ( N ) intersections numbered from 1 to ( N ) and ( M ) roads. The first GPS assigns a travel time ( P_i ) for road ( i ) and the second one a time ( Q_i ). For a road from intersection ( u ) to ( v ) with times ( P ) and ( Q ), if for the first GPS we have [ d_1(u) = P + d_1(v), ] then it does not complain; otherwise it complains (adding +1 to the total complaint count). Similarly, for the second GPS, if [ d_2(u) = Q + d_2(v), ] then no complaint occurs; otherwise, a complaint is recorded. Here, ( d_1(x) ) and ( d_2(x) ) denote the shortest travel times from intersection ( x ) to the farm (intersection ( N )) with respect to the first and second GPS measures respectively.

Your task is to determine the minimum total number of complaints Farmer John can receive while traveling from his house at intersection 1 to his farm at intersection ( N ). Note that if both GPS systems complain on a road, the complaint count increases by 2. It is guaranteed that there is at least one route from intersection 1 to intersection ( N ).

inputFormat

The first line contains two integers ( N ) and ( M ) (2 ( \leq N \leq 10,000 ), 1 ( \leq M \leq 50,000 )). Each of the following ( M ) lines contains four integers ( A_i ), ( B_i ), ( P_i ), and ( Q_i ), representing a directed road from intersection ( A_i ) to intersection ( B_i ) with travel times ( P_i ) and ( Q_i ) for the two GPS systems respectively.

outputFormat

Output a single integer: the minimum possible total number of complaints received on an optimal route from intersection 1 to intersection ( N ).

sample

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

0