Using the cut property that states that for any cut the edge with the smallest weight is contained in a MST.  So, could cut the graph up into pieces and run a O(n) (where n is edges) algorithm on each of the pieces.  Just need to show that merging is correct.