You are given an undirected, connected and weighted graph G(V, E), consisting of V number of vertices (numbered from 0 to V-1) and E number of edges.
Find and print the total weight of the Minimum Spanning Tree (MST) using Kruskal's algorithm.
By definition, a minimum weight 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.
Input Format :
The first input contains two integers, N and M, the number of vertices and edges in the graph respectively.
The next M input lines contains three integers X, Y and W each, representing each edge of the graph.
The edge X Y W represents an edge between vertices X and Y, having weight W.
The edges will be passed to the function as a array of arrays. Each array will contain 3 integers, X, Y, and W in that order.
Output Format :
Print the total weight of the minimum spanning tree.
You don't explicitly have to print anything, just return the total weight.
2 <= V <= 10^5
1 <= E <= 3 * 10^5
0 <= X < N
0 <= Y < N
1 <= W <= 10^4
where V and E represent the number of vertices and edges respectively.
X and Y represent the vertices between which there is an edge.
W is the weight of the edge.
Time limit: 1sec
Sample Input 1 :
0 1 3
0 3 5
1 2 1
2 3 8
Sample Output 1 :
Explanation for Sample Input 1:
The edge (2,3) having weight 8 will be excluded from the MST. The total weight of the MST then will be 1 + 3 + 5 = 9.
Sample Input 2:
1 2 6
2 3 2
1 3 2
1 0 2
Sample Output 2: