# Kruskal’s Minimum Spanning Tree Algorithm

Posted: 9 Jan, 2021

Difficulty: Moderate

#### You have been given a connected undirected weighted graph. Your task is to find the weight of the minimum spanning tree of the given graph.

#### A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles, and with the minimum possible total edge weight. A spanning tree’s weight is the sum of weights given to each edge of the spanning tree.

##### Input Format:

```
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains two integers ‘N’ and ‘M’ denoting the number of nodes and edges in the graph, respectively.
Each of the next ‘M’ lines contains three space integers ‘U’, ‘V’, and ‘W’. There is an undirected edge between node ‘U’ and ‘V’ of weight ‘W’.
```

##### Output Format:

```
For each test case, return the weight of the minimum spanning tree of the given graph.
```

##### Note:

```
You don't have to print the expected output, it has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 50
1 <= N <= 10000
1 <= M <= 10000
1 <= W <= 1000
1 <= U, V <= N
Time limit: 1 sec
```

SIMILAR PROBLEMS

Eulerian Circuit

Posted: 19 Jan, 2022

Difficulty: Hard

Minimum Swaps To Make Identical Array

Posted: 22 Jan, 2022

Difficulty: Moderate

Find Center of Star Graph

Posted: 26 Jan, 2022

Difficulty: Easy

Critical Connections in a Network

Posted: 27 Jan, 2022

Difficulty: Hard

Critical Connections in a Network

Posted: 27 Jan, 2022

Difficulty: Hard

COUNT ISLANDS

Posted: 14 Sep, 2022

Difficulty: Moderate