Minimum Cost to Connect Agents

You are given N agents and M possible connections between them. Each connection links two agents and has an associated cost. Your task is to determine the minimum total cost required to connect all agents so that each agent is reachable from every other agent, either directly or indirectly.

This problem can be modeled as finding a Minimum Spanning Tree (MST) of a weighted undirected graph. Specifically, if we denote the set of edges chosen in the MST by \(E_{MST}\), then the total cost is given by:

[ S = \sum_{e \in E_{MST}} w(e), ]

If it is impossible to connect all agents (i.e. the graph is disconnected), output -1.

inputFormat

The first line of input contains two integers N and M, representing the number of agents and the number of connections, respectively.

Each of the following M lines contains three integers u, v and w, where u and v are the indices of the agents (1-indexed) and w is the cost to connect them.

outputFormat

Output a single integer: the minimum total cost to connect all agents. If it is not possible to connect all agents, output -1.

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

6