Prim's Algorithm

Given the number of vertices n and bidirectional edge information edges, write a function solution that applies Prim's algorithm starting from vertex 1 and returns the vertex numbers included in the minimum spanning tree (MST), in the order they are processed.

If there are multiple vertices at the same minimum distance during the Prim's algorithm process, prioritize the vertex with the smaller vertex number.

It is assumed that the input graph is connected (a path exists between any two vertices).
The graph always guarantees the existence of an MST.

Concept Explanation

The Minimum Spanning Tree (MST) refers to a spanning tree of a given bidirectional graph with the minimum total edge weight.
Reference: Minimum Spanning Tree

Two common algorithms to find an MST are Prim's algorithm and Kruskal's algorithm.

Prim's algorithm proceeds as follows:

1. Start with an arbitrary vertex, including it in the set S.
2. Calculate the distance of vertices not included in S from S.
3. Add the vertex with the smallest distance and its corresponding edge to S and the MST.
4. Repeat steps 2 and 3 until all vertices are included in S.

There are two implementations of Prim's algorithm:
Using a list has a time complexity of $O(V^2)$, while using a priority queue (min-heap) has a time complexity of $O(E \log V)$.

For example, consider the following connected graph and assume that Prim's algorithm starts from vertex 1:

At the start, the set S, MST, and the distance of each vertex from S are initialized as follows:

The vertex with the smallest distance from S is vertex 2, so it is added to S, and the edge weight is added to the MST total weight.
Update the distances of vertices connected to vertex 2:

Next, vertex 3 is added to S, and the process repeats:

The next vertex with the smallest distance is vertex 6, which is added to S, and the process continues:

If there are multiple vertices with the same minimum distance, any vertex can be included in S without affecting the MST.
In this example, vertex 4 is added first due to its smaller vertex number:

Finally, vertex 5 is added to S. Once all vertices are included in S, the algorithm terminates:

In this example, the MST total weight calculated using Prim's algorithm is 14.

Constraints

• The number of vertices n is a natural number between 2 and 5,000 inclusive.
• Each element in edges represents a bidirectional edge with two endpoints x, y, and edge weight w:
  • edges contains up to 1,000,000 edges.
  • x, y are natural numbers between 1 and n inclusive.
  • w is a natural number up to 10,000 inclusive.

Test Case

Explanation for Test Case 1

• This corresponds to the example graph described in the explanation above.

Explanation for Test Case 2

• The given graph is already a tree. From vertex 1, vertices 3 and 2 are sequentially added to the MST. Between vertices 4 and 5, which have equal edge weights, vertex 4 is added first due to its smaller vertex number.