The Floyd-Warshall all-pairs shortest path algorithm (section 25.2 of CLRS) computes, for each pair of vertices u, v, the shortest path from u to v. However, if the graph has negative cycles, the algorithm fails. Describe a modified version of the algorithm (with the same asymptotic time complexity) that correctly returns shortest-path distances, even if the graph contains negative cycles. That is, if there is a path from u to some negative cycle, and a path from that cycle to v, the algorithm should output as the length of the shortest path from u to v. For other pairs of vertices the algorithm should correctly find the length of the shortest directed path.