Find a MST such that it's mostly red (original graph's edges are colored red and blue) Consider the following problem:
Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight).
Find an efficient algorithm to find an MST which is mostly red (meaning, has the most red edges possible).

I think this can be done in linear time, in O(n+m) complexity using either Kruskal or Prim's algorithms, but I can't find an algorithm to do that.

I thought about diving the edges into two groups - red and blue, and then running Kruskal's algorithm on the red edges first, and then if we still don't have |V|-1 edges in the MST we have so far, run Kruskal again on the blue edges.
However, this algorithm doesn't solve the given problem since we might not end up with a tree, but rather with a forest (made up of two trees).

Please advise.
Hint: Add $\epsilon&gt;0$ to the weight of all blue edges. (This is equivalent to the suggestion Raphael made in his comment.)