Find a MST such that it's mostly red (original graph's edges are colored red and blue)
Hint: Add $\epsilon&gt;0$ to the weight of all blue edges. (This is equivalent to the suggestion Raphael made in his comment.)