Proof of correctness \\
Let $e$ be the first edge we add that is inconsistent with any MST, and left $F$ be the
forest just before adding this edge. Let $M$ be an MST consistent with $F$. Put $e$ into M.
Since $M$ is a tree, this must create a cycle. Now consider tracing a path through this cycle,
considering only the edges connecting the individual trees in $F$ . It must be true that there
is some $e' > e$. \\
Why? Start at the tree that we marked $e$ from. There must be another edge incident to the
tree in our cycle. If this edge (our $e'$) was not marked by our algorithm, then $e < e'$
and we can remove $e'$ and use $e$, creating a better tree. This contradicts our definition of e. \\
Now, instead assume that this edge (lets call it $e_1$) was
marked, so it must have been marked by another tree. Since we didn't mark it, $e < e_1$. We
can continue around the cycle, and eventually we must find an unmarked edge. Since each time
we traverse, we'll have $e < e_1 < e_2 < ... e_k$ the unmarked node must be our $e' > e$
and thus it can be removed, creating a smaller sum MST, and contradicting our
definition of $e$ \\