You are given a directed, weighted graph G = (V, E, w), in which the edge-weights are integers bounded in absolute value by some fixed polynomial in n (the number of vertices). The graph is given in adjacency list format-specifically, for each vertex you are given a list of its out-neighbors and the corresponding edge weights. However the graph is given on a read-only memory medium. At your disposal you have another memory, which is read-write, but can hold only O(log^2 n) bits. Show how you can, given vertices s, t belongsto V, compute the length of a shortest s path or else determine that the graph has a negative-weight cycle