If you allow twice the solution, you can do it in O(m log n) time using MST.