Maximum Spanning Tree

You are given an undirected weighted graph with N nodes and M edges. The task is to compute the total weight of the maximum spanning tree (MST) of the graph. In other words, you need to select N-1 edges such that the graph is connected and the sum of the weights of the chosen edges is maximized.

The maximum spanning tree is similar to the minimum spanning tree except that instead of choosing the edges with the smallest weights, you choose the edges with the largest weights while still avoiding cycles. One popular algorithm to solve such problems is Kruskal's algorithm combined with a union‐find data structure.

The weight of the maximum spanning tree can be computed using the following formula:

\( \text{MST}_{\max} = \sum_{e \in T} w(e) \)

where \(T\) is the set of edges in the maximum spanning tree and \(w(e)\) is the weight of edge \(e\).

inputFormat

The input is read from standard input. The first line contains two integers N and M, representing the number of nodes and the number of edges respectively. The following M lines each contain three integers u, v, and w, indicating that there is an edge between nodes u and v with weight w.

Note: The nodes are numbered from 1 to N.

outputFormat

Output a single integer representing the total weight of the maximum spanning tree. The result should be printed to standard output.

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

12