The following algorithm attempts to find the minimum spanning tree of a connected $($undirected$)$ graph G

with $($potentially negative$)$ integer edge weights.

$$ Simultaneously add $1$ to every edge weight. Keep doing this until every edge has positive weight.

$$ Find the MST of this new graph $($where all the edge weights are positive$),$ using an algorithm we already

know, such as Prim.

If it works, explain why. If not, give a connected graph G where it fails $($and show what happens when you

run the algorithm on it$).$