Description

Given a simple, undirected weighted graph G = (V, E, W), output the weight of its minimum spanning tree.

Input

The input includes multiple test cases. The first of the input is an integer T (T <= 1000) specifying the number of test cases. For each case, the first line contains two integers: the number of the node N and the number of the edges M. In the following M lines, each line contains three integers (s_i, e_i, c_i), 1 <= s_i, e_i <= N, 1 <= c_i <= 100, representing the indices of end vertices of an edge and the weight of the edge.

Case 1: 2 <= N <= 10², 1 <= M <= 10³
Case 2: 2 <= N <= 10³, 1 <= M <= 10³
Case 3: 2 <= N <= 10³, 1 <= M <= 10⁴
Case 4: 2 <= N <= 10³, 1 <= M <= 10⁵

Output

For each case, output a single line that indicates the weight of the minimum spanning tree of the graph.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss