PROBLEM 1 (25 POINTS) Give a polynomial-time algorithm that solves the following problem. Give a clear proof that your algorithm is correct and runs in polynomial time. Input: a simple (no repeated edges or self-loops), connected, undirected graph G = (V, E) with a positive edge-weight function w: E N+, with all edge weights distinct; Output: a spanning tree T C E of G, of second-smallest total weight. More precisely: T should have minimum weight among all spanning trees of G that are not Minimum Spanning Trees for (G,w). If there are two or more such trees, you are free to output any one of them, and you don't need to decide whether such a tie can or does occur. PROBLEM 1 (25 POINTS) Give a polynomial-time algorithm that solves the following problem. Give a clear proof that your algorithm is correct and runs in polynomial time. Input: a simple (no repeated edges or self-loops), connected, undirected graph G = (V, E) with a positive edge-weight function w: E N+, with all edge weights distinct; Output: a spanning tree T C E of G, of second-smallest total weight. More precisely: T should have minimum weight among all spanning trees of G that are not Minimum Spanning Trees for (G,w). If there are two or more such trees, you are free to output any one of them, and you don't need to decide whether such a tie can or does occur