Finding MST for connected graph with $|E|=|V|+87$

Given $G=(V,E)$ undirected, connected graph and weights given by $w:E \to \mathbb R$. We also know that $|E|=|V|+87$.

Find Minimum spanning tree of $G$.

Obviously we can use Prim in $O(|V| \cdot \log |V|)$.

But can we do better by using the fact that the graph is connected, and use the sets sizes? Like removing the lightest edge from each cycle and keeping the connectivity of the graph?

The "Cycle Property" helps (If you don't know it before, try to prove it first):


Let $C$ be any cycle in $G$ and $e$ a heaviest (not necessarily unique) edge in $C$. Then there exists some MST which does not contain $e$.

You are encouraged to answer the following questions:

• How to identify a cycle and then a heaviest edge $e$ in it?

• What to do with the edge $e$?

• How many times should you apply the cycle property?

• When to stop?

Then analyze the time complexity.

StackExchange Computer Science Q#77698, answer score: 3