Minimum Total Maintenance Cost

You are given an undirected graph representing a network of servers connected by various links. Each connection has a maintenance cost and is described by three integers (a, b, c), where a and b are the endpoints (using 1-indexing) and c is the cost to maintain that connection. Your task is to optimize the network by selecting a subset of the connections such that all servers remain connected and the total maintenance cost is minimized.

This essentially requires you to compute a Minimum Spanning Tree (MST) of the given graph. In particular, based on the well-known Kruskal's algorithm, you need to select edges such that the sum of their weights (costs) is minimized. Mathematically, if E' is the set of edges chosen, then you need to minimize:

$$\sum_{(a,b,c) \in E'} c$$

while ensuring that the graph remains connected. The graph is guaranteed to be connected.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains two space-separated integers n and m denoting the number of servers (nodes) and the number of connections (edges), respectively.
• The following m lines each contain three space-separated integers a, b, and c representing a connection between server a and server b with maintenance cost c.

Note: The servers are 1-indexed.

outputFormat

Output a single integer to stdout representing the minimum total maintenance cost required to keep the network fully connected.

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

4