Running Time

We compute an MST on n² edges: $O(n^2 \log n)$.

We then walk the tree, avoiding duplicates: O(n).

Total: $O(n^2 \log n)$ (not too bad).