 Solution

To find a minimum-weight acyclic subgraph, filter to the subgraph $G_{-}$ containing only strictly negative-weight edges, and run Kruskal's algorithm on those edges, accepting an edge exactly when it joins different current components. Return the resulting forest, with any omitted vertices regarded as isolated. Zero-weight edges may be omitted without worsening the objective.

To prove correctness, first remove all nonnegative edges from any feasible acyclic graph; removing them preserves acyclicity and cannot increase weight. Thus an optimum using only negative edges exists. Inside a connected component of $G_{-}$, any forest not yet connected can be extended by a negative crossing edge: some such edge exists because the original component is connected. Adding it preserves acyclicity and strictly reduces total weight. Consequently an optimum must span each component of $G_{-}$, and its restriction there must be a minimum spanning tree. Kruskal's algorithm finds exactly the resulting minimum spanning forest of $G_{-}$. This proves optimality among all acyclic subgraphs, including disconnected ones.

With $m_{-}$ negative edges, filtering costs $O(|V|+|E|)$, sorting costs $O(m_{-}\log (m_{-}+1))$, and the union-find operations take $O((|V|+m_{-})\alpha (|V|))$ time. A standard overall bound is $O(|V|+|E|\log (|E|+1))$ time. If there are no negative edges, the empty edge set is optimal.