Finding edges with minimal weight sum, such that every simple cycle contain at least one edge
To turn some of my hints into an answer, the problem with your solution is that the DFS phase doesn't do anything to optimize the weight of the complement of the tree.  Here is a solution.

Let $G=(V,E)$ be your graph, $w : E\to \mathbb{Z}$ the weight function, which we extend linearly to $2^E$.  Call the set we are looking for $B$.

Property (1) implies that $C := E\setminus B$ is acyclic.  Otherwise, $C$ contains some cycle, contradicting the fact that $B\cap X\neq \emptyset$ for every cycle $X$ in $G$.

Property (2) implies that $w(C)$ should be as large as possible.  Since $w(B) = w(E) - w(C)$, minimizing $w(B)$ is just maximizing $w(C)$.

So, the algorithm is just to compute the maximum weight forest in $G$, and return the complement.  (The MWF isn't necessarily a spanning tree if there are negative weights.)