1. Let G(V, E) be a graph with arbitrary weights on its edges (could be positive or negative). Assume that it is known that for every pair u, v, the shortest path u v contains only