Minimum Spanning Tree

In this problem, you are given a connected, undirected weighted graph with n vertices and m edges. The vertices are numbered from 1 to n, and the graph can contain multiple edges between the same pair of vertices as well as self-loops. Your task is to find a spanning tree (i.e., a tree connecting all vertices) such that the sum of the weights of the chosen edges is minimized. This is the classic Minimum Spanning Tree (MST) problem.

Recall that a spanning tree is a subset of edges that connects all vertices without any cycles, and with exactly n-1 edges. Any edge that forms a cycle should be skipped. Self-loops should also be ignored since they cannot contribute to a spanning tree.

The answer must be computed using MST algorithms like Kruskal's or Prim's algorithm. Edge weights are given by non-negative integers.

The formula for the MST weight sum can be expressed in LaTeX as follows:

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

inputFormat

The first line contains two integers n and m separated by a space.

Each of the following m lines contains three integers: u, v, and w, indicating there is an edge between vertex u and vertex v with weight w.

You can assume that the graph is connected.

outputFormat

Output a single integer, which is the minimum total weight of the spanning tree.

sample

3 3
1 2 1
2 3 2
1 3 3

3