2. [20 points] We are given a directed, weighted graph G (V,E), where each edge (u,u) E has a weight E(u, >0. Let s and t be two nodes in V. Give an efficient algorithm for finding the shortest path from s to t where you have the option to pick one edge and change its weight to 0. (Hint: you'll need the following simple but useful observation. For a node v in G, a shortest path from v to t in the weighted graph G is also a shortest path from t to v in the (weighted) reverse graph of G, and vice versa