A complete graph is a graph where every pair of nodes has an edge. With n nodes, you have 2n(n−1) edges. For this problem, generating all edges upfront takes O(n2) time and space. That is acceptable for small n (up to 1000).
Kruskal still works, but you will spend time sorting O(n2) edges. Prim might be faster here because it does not require generating all edges upfront. Think about the tradeoff.