Minimum Network Bandwidth

You are given n routers and m possible connections between them. Each connection has an associated bandwidth cost. Your task is to connect all routers to the main server (router 1) with the minimum total bandwidth cost. Essentially, you need to construct a Minimum Spanning Tree (MST) of the network.

If it is impossible to connect all routers, output -1.

The total bandwidth cost is given by \(\sum_{e \in MST} w_e\), where \(w_e\) is the cost of each connection in the MST.

inputFormat

The first line contains two integers n and m (number of routers and number of connections, respectively).

Then m lines follow, each containing three integers u v w indicating there is a connection between router u and router v with a bandwidth cost of w.

Input is provided via standard input (stdin).

outputFormat

Output a single integer representing the minimum total bandwidth required to connect all routers. If it is not possible to connect all routers, output -1.

Output is printed to standard output (stdout).

5 7
1 2 10
1 3 20
2 3 30
2 4 25
3 5 15
4 5 40
3 4 35

70