Minimum Spanning Tree Construction

Given an undirected weighted graph representing a network of cities and roads, your task is to compute the minimum total weight required to connect all the cities. The graph is defined by n cities and m roads. Each road is described by three integers u, v, and w, where u and v denote the cities the road connects and w is its weight. You are required to use Kruskal's algorithm (or any equivalent approach) to find the MST (Minimum Spanning Tree) of the graph.

The MST of a graph is a tree that connects all the vertices together, with the minimum possible total edge weight. The problem can be mathematically expressed as finding a subset E' of edges such that:

Note that the input is given via standard input (stdin) and your output should be produced to standard output (stdout). It is guaranteed that the graph is connected.

inputFormat

The first line contains two integers n and m, where n is the number of cities and m is the number of roads. The following m lines each contain three integers u, v, and w representing a road between cities u and v with weight w.

outputFormat

Output a single integer representing the total weight of the minimum spanning tree.## sample

4 5
1 2 1
1 3 4
1 4 3
2 3 2
3 4 5

6