P3106 [USACO14OPEN] Dueling GPSs S

Farmer John has recently purchased a new car online, but in his haste he accidentally clicked the "Submit" button twice when selecting extra features for the car, and as a result the car ended up equipped with two GPS navigation systems! Even worse, the two systems often make conflicting decisions about the route that FJ should take. The map of the region in which FJ lives consists of N intersections (2

无

无

There are 5 intersections and 7 directional roads. The first road connects from intersection 3 to intersection 4; the first GPS thinks this road takes 7 units of time to traverse, and the second GPS thinks it takes 1 unit of time, etc. If FJ follows the path 1 -> 2 -> 4 -> 5, then the first GPS complains on the 1 -> 2 road (it would prefer the 1 -> 3 road instead). However, for the rest of the route 2 -> 4 -> 5, both GPSs are happy, since this is a shortest route from 2 to 5 according to each GPS.