Minimum Spanning Tree

Problem

Given the number of vertices n and bidirectional edge information edges, write a function solution that returns the total weight of the minimum spanning tree (MST).

It is assumed that the input graph is a connected graph (a graph where a path exists between any two vertices).
The graph always guarantees the existence of a minimum spanning tree.

Concept Explanation

A Minimum Spanning Tree (MST) refers to a spanning tree of a given bidirectional graph that has the minimum total edge weight.

To understand MST, it is essential to first understand a "Spanning Tree." A spanning tree is a subgraph of a given bidirectional graph that includes all the vertices and has a tree structure.

Consider the following bidirectional graph:

From this graph, the following subgraphs can be considered. However, the first subgraph is not a tree, and the second subgraph does not include all vertices, so neither is a spanning tree.

Examples of spanning trees for this graph are as follows:

Among these, the total weight of the edges in the first spanning tree is 24, while the total weight in the second spanning tree is 17.
Even when considering all other spanning trees, the minimum total weight of the tree is 17, making the second spanning tree the MST.
In general, multiple MSTs with the same minimum total weight may exist for a given graph.

Constraints

• The number of vertices n is a natural number between 2 and 10,000 inclusive.
• Each element of edges represents a bidirectional edge with two endpoints x, y and the edge weight w:
  • 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, and the graph itself becomes its MST. In this case, the total weight of all edges is 19.