You have a directed graph with N cities and M flights. Find these four values for paths starting at city and ending at city N:
Shortest distance.
Number of shortest paths (mod ).
Minimum flights on a shortest path.
Maximum flights on a shortest path. Constraints: , M ≤ . All four answers come from a single modified Dijkstra run where you maintain extra arrays alongside the distance array.