This takes O(n²) time. With an explicit, sparse similarity matrix instead of distances, it can be done in O(E lg(E)) time where E are the edges of the similarity graph, i.e. the non-zero similarities. In the optimal algorithm, you don't even need to build the spanning tree. By promising to return the spanning tree and working with metrics instead of similarities, we're tying ourselves down to a suboptimal algorithm.