Minimum Communication Cost

You are given a network of N computers and M potential connections between them. Each connection is described by two endpoints and a weight representing the communication cost. Your task is to determine the minimum total communication cost required to connect all the computers. If it is impossible to connect all computers (i.e. the network is disconnected), output -1.

The problem can be solved by finding a minimum spanning tree (MST) of the graph. If the graph does not have a spanning tree that covers all nodes, then the network cannot be fully connected.

Input Format: The first line contains two integers N and M. Each of the next M lines contains three integers u, v and w representing a connection between computers u and v with cost w.

Output Format: Output a single integer which is the minimum total cost to connect all computers, or -1 if it is impossible.

inputFormat

The input is read from standard input (stdin). The first line contains two space-separated integers N and M indicating the number of computers and the number of connections, respectively. This is followed by M lines, each containing three integers u, v, and w where u and v are the endpoints of a connection and w is its communication cost.

outputFormat

The output is a single integer printed to standard output (stdout). This integer is the minimum communication cost to connect all computers, or -1 if it is not possible.

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

6