Dueling GPSs

Farmer John accidentally ordered two GPS units for his new car. Both use the same map, but each assigns its own travel time to every road.

The map has $N$ intersections ($2 \le N \le 10\,000$) and $M$ one-way roads ($1 \le M \le 50\,000$). Road $i$ runs from $A_i$ to $B_i$. Multiple roads may connect the same pair of intersections, and a two-way road appears as two opposite one-way roads. FJ's house is at intersection 1 and his farm at intersection $N$. The farm is reachable from the house.

Road $i$ takes $P_i$ time according to the first GPS and $Q_i$ time according to the second (each is an integer in $1 \ldots 100\,000$).

When FJ travels from his house to the farm, a GPS complains whenever he uses a road that it does not consider part of any shortest route from the current intersection to the farm. If both GPS units complain on the same road, that adds 2 to the total.

Find the minimum total number of complaints over all routes from 1 to $N$.

• Line 1: $N$ and $M$.
• Next $M$ lines: $A_i$, $B_i$, $P_i$, $Q_i$.

The minimum total number of complaints.

Precompute shortest distances to the farm for each GPS, then mark roads that are not on any shortest-path edge as complaints.