title: Algorithm to find minimum spanning tree for graph with edge weights in {1,2,3}
body: <p>I have recently been doing some research into Prims/Kruskals algorithms for finding minimum spanning trees in graphs, and I am interested in the following problem:</p>
  
  <p><strong><em>Let G be an undirected graph on n vertices with m edges, such that each edge has a weight w(e) ∈ {1, 2, 3}. Is there an algorithm which finds a minimum spanning tree of G in time O(n+m)?</em></strong></p>
  
  <p>Obviously, you could just run Prims on the graph, and you would get a minimum spanning tree, but not in the required time.</p>
  
  <p>I was thinking that we could start by adding every edge with weight 1 to the tree, provided it creates no cycles, as if there is an edge of weight 1 that creates no cycles, then it is preferable to an edge of weight 2 say, and do this in increasing order.</p>
  
  <p>Any help on possible ways to design an algorithm to do this would be appreciated and any implementations (java preferable but any language welcome) would be super helpful.</p>