Maximum Spanning Tree Weight

In this problem, you are given an undirected graph with (n) nodes and (m) edges. Each edge has an associated weight. Your task is to compute the weight of the maximum spanning tree (MST) of the graph. A spanning tree is a subgraph that connects all nodes with no cycles, and the maximum spanning tree is the one where the sum of the weights of the edges is maximized. You can use Kruskal's algorithm with a union-find (disjoint set union) structure to solve this problem. The weight of the maximum spanning tree can be expressed by the formula (W = \sum_{e \in E_T} w(e)), where (E_T) represents the set of edges in the spanning tree and (w(e)) is the weight of an edge.

inputFormat

The input begins with an integer (T) (the number of test cases). Each test case is described as follows: (n) (m): Two integers, the number of nodes and the number of edges, respectively. Next line: (n) space-separated integers representing the weights of the nodes (note: these weights are provided for compatibility but not used in the MST calculation). Following (m) lines: Each line contains three integers (u), (v), and (w) representing an edge between nodes (u) and (v) with weight (w). You may assume that node indices are 1-indexed.

outputFormat

For each test case, output a single integer on a new line, representing the weight of the maximum spanning tree of the graph.## sample

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

15