Dueling GPSs

Interview

Time limit1sMemory limit128 MB

Summary

Find a route from intersection 1 to N that minimizes the count of roads lying off either GPS shortest path to the farm.

Level: Medium6 of 10
Topics: Shortest path, Graph
Solved: No attempts yet

Problem

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$ .

Input

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

Output

The minimum total number of complaints.

Hint

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

Examples5

Example 1

Input

Expected output

Example 2
Input
```
3 3
1 2 5 19
2 3 3 9
1 3 49 29
```
Expected output
```
0
```

Example 3

Input

Expected output

Example 4

Input

Expected output

Example 5

Input

Expected output