Minimum Spanning Tree

Problem Given a weighted, connected, undirected graph, find a Minimum Spanning Tree — a cycle-free subset of edges that connects every vertex with the minimum possible total edge weight.

Input / Output

• Input: V vertices and a list of weighted undirected edges (u, v, w)
• Output: the total weight of the MST, and optionally the V-1 edges forming it

Constraints

• Up to 10^4–10^5 vertices and edges
• Graph is connected (otherwise the answer is a minimum spanning forest)
• Edge weights may repeat, so the MST is not necessarily unique — its total weight always is

Example

• Edges (A-B, 1), (B-C, 2), (A-C, 3) → MST picks A-B and B-C for total weight 3, skipping the redundant A-C
• Tricky case: equal-weight edges give several valid MSTs of identical cost — confirm whether any one is acceptable