Minimum Spanning Tree Problem

You are given a weighted undirected graph that represents a park where each node is a park and each edge is a bidirectional path between parks. Your task is to compute the Minimum Spanning Tree (MST) of the graph, which connects all parks with the minimum total path length. If it is impossible to connect all parks, output -1.

The total weight of the MST is given by the formula \(\sum_{i=1}^{n-1} w_i\), where \(w_i\) represents the weight of each selected edge.

inputFormat

The input is provided via standard input (stdin) in the following format:

T
n m
u1 v1 w1
u2 v2 w2
... (m lines for edges)

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers n and m representing the number of parks (nodes) and paths (edges) respectively.
• Then follow m lines, each containing three space separated integers u, v, and w, which denote a path between park u and park v with length w.

outputFormat

For each test case, print a single integer on a new line: the total weight of the Minimum Spanning Tree. If it is not possible to connect all parks, print -1.

## sample

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

6

</p>