Minimum Spanning Tree Sum

In this problem, you are given a connected weighted undirected graph with (n) nodes and (m) edges. The nodes are numbered from 1 to (n). The graph may contain multiple edges between the same pair of nodes and self-loops. Your task is to find a spanning tree (a subgraph that connects all the vertices with exactly (n-1) edges and no cycles) such that the sum of the weights of the edges in the spanning tree is minimized. In other words, you need to compute the sum of the edge weights in the Minimum Spanning Tree (MST).

The MST's total weight can be expressed by the formula:

where (T) is the set of edges in the MST and (w_e) is the weight of an edge (e). You may use classical MST algorithms such as Kruskal's or Prim's algorithm to solve the problem.

inputFormat

The first line contains two integers (n) and (m), representing the number of nodes and edges, respectively. Each of the following (m) lines contains three integers (u), (v), and (w) describing an edge between node (u) and node (v) with a weight of (w). Note that self-loops (where (u = v)) should be ignored.

outputFormat

Output a single integer representing the total weight of the Minimum Spanning Tree.

sample

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

6