You are given a connected undirected graph with n vertices labelled 0..n-1 and m weighted edges. A spanning tree keeps n-1 edges so that all vertices stay connected. Its weight is the sum of the chosen edge weights.
Report the minimum possible total weight of a spanning tree.
Input format
Line 1: two integers n and m.
The next m lines each contain three integers u v w, an undirected edge between u and v with weight w.
Output format
A single integer: the minimum spanning tree total weight. (For n = 1 the answer is 0.)
Constraints
- 1 <= n <= 2000
- 0 <= m <= 20000
- 0 <= u, v <= n - 1 and u != v
- 1 <= w <= 100000
- The graph is guaranteed connected. Parallel edges may exist.