Minimum Activation Cost

You are given a network of machines and cables connecting pairs of machines. Each cable has an activation cost. The task is to determine the minimum cost required to activate a subset of cables so that all machines become connected. In other words, you need to compute the cost of a minimum spanning tree (MST) of the given graph.

If the graph does not have an MST (i.e. not all machines are connected), output -1.

Formally, you are given a graph with $N$ nodes and $M$ edges. Each edge is represented by a tuple $\left(u, v, w\right)$, where $u$ and $v$ are the connected machines and $w$ is the activation cost. The goal is to find a subset of edges such that all nodes are connected and the total cost $\sum_{e \in MST} w(e)$ is minimized.

You may use algorithms such as Kruskal's or Prim's to solve this problem.

inputFormat

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

• The first line contains a single integer $T$, the number of test cases.
• For each test case:
  • The first line contains two integers $N$ and $M$, representing the number of machines and the number of cables, respectively.
  • The following $M$ lines each contain three integers $u$, $v$, $w$, where $u$ and $v$ denote the machines connected by a cable and $w$ is the activation cost of that cable.

outputFormat

For each test case, output a single line containing one integer. This integer is the minimum activation cost (i.e., the sum of the weights of the selected cables) to connect all machines. If it is impossible to connect all machines, output -1.

## sample

2
4 5
1 2 3
2 3 4
3 4 5
1 4 6
2 4 7
3 3
1 2 1
2 3 2
1 3 4

12
3

</p>