Minimum Spanning Tree in the City

You are given a city with D districts and R rail lines connecting these districts. Each rail line is represented as a triplet (u, v, w) where u and v are two distinct districts and w is the travel time between them. Your task is to compute the total travel time of the Minimum Spanning Tree (MST) that connects all the districts. In other words, select a subset of rail lines that connects all districts with the minimum possible sum of travel times.

The solution can be derived by using Kruskal's algorithm which finds the MST by sorting edges and connecting the districts while avoiding cycles. The formula for the total travel time can be represented in LaTeX as follows:

$$ MST = \sum_{e \in T} w_e $$

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

inputFormat

The first line of input contains two integers: D, the number of districts, and R, the number of rail lines.

The next R lines each contain three integers u, v, and w, where u and v are the endpoints (district numbers) and w is the travel time for that rail line.

You may assume that 1 \leq u, v \leq D and all travel times are positive integers.

outputFormat

The output is a single integer representing the total travel time of the minimum spanning tree, which is the sum of the travel times of the selected rail lines.

If the districts cannot be fully connected then the problem guarantees that a solution will exist.

## sample

4 5
1 2 10
2 3 15
3 4 4
4 1 6
1 3 5

19