Minimum Spanning Tree

You are given an undirected connected graph with N nodes numbered from 1 to N and M weighted edges. Your task is to compute the Minimum Spanning Tree (MST) of the graph using Kruskal's algorithm. The MST is a spanning tree with the minimum total weight and exactly N-1 edges. If there are multiple valid MSTs, output the one whose list of edges is lexicographically smallest (comparing by weight first, then the two endpoints).

Note: Use union-find (disjoint set union) for efficient cycle detection. All edges in the output should be sorted lexicographically.

Input: The first line contains two integers N and M. Each of the next M lines contains three integers u, v, and w indicating that there is an edge between nodes u and v with weight w.

Output: Output the total weight of the MST on the first line. Then output each edge in the MST on a new line as three space-separated integers u, v, and w. The edges should be printed in lexicographical order.

inputFormat

The input is read from stdin and has the following format:

N M
u1 v1 w1
u2 v2 w2
... 
 uM vM wM

Where:

• N is the number of nodes.
• M is the number of edges.
• Each edge is represented by three integers u, v, w that denote an undirected edge between nodes u and v with weight w.

outputFormat

The output is written to stdout with the following format:

T
u1 v1 w1
u2 v2 w2
...

Where:

• T is the total weight of the MST.
• The following N-1 lines list the edges in the MST in lexicographical order, each formatted as three space-separated integers.

## sample

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

6
1 2 1
1 3 2
3 4 3

</p>