Farmer John has recently purchased a new car online, but in his haste heaccidentally clicked the "Submit" button twice when selecting extrafeatures for the car, and as a result the car ended up equipped with twoGPS navigation systems! Even worse, the two systems often make conflictingdecisions about the route that FJ should take.The map of the region in which FJ lives consists of N intersections(2 <= N <= 10,000) and M directional roads (1 <= M <= 50,000). Road iconnects intersections A_i (1 <= A_i <= N) and B_i (1 <= B_i <= N). Multiple roads could connect the same pair of intersections, and abi-directional road (one permitting two-way travel) is represented by twoseparate directional roads in opposite orientations. FJ's house is locatedat intersection 1, and his farm is located at intersection N. It ispossible to reach the farm from his house by traveling along a series ofdirectional roads.Both GPS units are using the same underlying map as described above;however, they have different notions for the travel time along each road. Road i takes P_i units of time to traverse according to the first GPS unit,and Q_i units of time to traverse according to the second unit (eachtravel time is an integer in the range 1..100,000).FJ wants to travel from his house to the farm. However, each GPS unitcomplains loudly any time FJ follows a road (say, from intersection X tointersection Y) that the GPS unit believes not to be part of a shortestroute from X to the farm (it is even possible that both GPS units cancomplain, if FJ takes a road that neither unit likes). Please help FJ determine the minimum possible number of total complaints hecan receive if he chooses his route appropriately.
