Minimal Path Count in a Road Network

In a growing road network, finding the best (or minimal) path between two cities is a realistic problem. Each road is bidirectional and has a fixed travel time and a toll (fee). A path is defined as a sequence of roads. The total travel time is the sum of the travel times of each road and the total cost is the sum of the tolls on the path.

A path \( P \) is considered better than another path \( Q \) if either:

• \( P \) is strictly faster than \( Q \) (i.e. \( t(P) < t(Q) \)) and the cost is no more than that of \( Q \) (i.e. \( c(P) \le c(Q) \)), or
• \( P \) is strictly cheaper than \( Q \) (i.e. \( c(P) < c(Q) \)) and the travel time is no more than that of \( Q \) (i.e. \( t(P) \le t(Q) \)).

A minimal path is one for which no other path exists that is better according to the above criteria. Note that there might be more than one minimal path. Also, if two minimal paths have identical total travel time and cost, they are considered the same.

The problem is to count the number of distinct minimal paths (i.e. distinct pairs \((t, c)\)) from city 1 to city \( n \) in the given road network. If no path exists, output 0.

Note: Use multi-objective optimization to compute the minimal pairs. The Pareto optimality condition is defined as: For two paths with (time, cost) pairs \((t_1, c_1)\) and \((t_2, c_2)\), if \(t_1 \le t_2\) and \(c_1 \le c_2\) with at least one strict inequality, then the first path dominates the second.

inputFormat

The input starts with two integers \( n \) and \( m \) (where \( n \) is the number of cities and \( m \) is the number of roads). Each of the following \( m \) lines contains four integers \( u\), \( v\), \( t \), and \( c \) which represent a road connecting city \( u \) and city \( v \) with a travel time of \( t \) and a toll of \( c \). Roads are bidirectional. Assume that cities are numbered from 1 to \( n \), and the starting city is 1 while the destination is \( n \).

outputFormat

Output a single integer which is the count of distinct minimal paths (distinct \((time, cost)\) pairs) from city 1 to city \( n \). If there is no path from city 1 to city \( n \), output 0.

sample

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

1