Unique Minimum Cost Road Network

You are given a set of towns and a list of potential bidirectional roads connecting them. Each road has an associated construction cost. Your task is to choose a subset of these roads to build a road network so that every pair of towns is connected by exactly one unique minimum-cost path.

This problem can be modeled as finding a Minimum Spanning Tree (MST) in an undirected weighted graph. Recall that if a spanning tree covers all n nodes, then it must contain exactly n-1 edges and the total cost is given by \[ \text{Cost} = \sum_{e \in T} w_e, \] where \(w_e\) is the weight of edge \(e\) and \(T\) is the set of chosen edges.

If it is impossible to construct such a network (i.e. the graph is disconnected), output -1.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains a single integer T denoting the number of test cases.

For each test case:

• The first line contains two integers n and m, where n is the number of towns and m is the number of potential roads.
• Each of the next m lines contains three integers u, v, and w representing a road connecting town u and town v with a construction cost of w.

Note: Towns are numbered starting from 1.

outputFormat

For each test case, print a single line to standard output (stdout) containing one integer: the minimum construction cost to build the road network with a unique minimum-cost path between any pair of towns. If it is impossible to construct such a network, print -1.## sample

2
4 5
1 2 2
1 3 5
2 3 7
2 4 8
3 4 3
4 4
1 2 1
2 3 1
3 4 1
1 3 2

10
3