You have been given a connected undirected weighted graph. Your task is to find the weight of the minimum spanning tree of the given graph.

A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles, and with the minimum possible total edge weight. A spanning tree’s weight is the sum of weights given to each edge of the spanning tree.

Input Format:

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two integers ‘N’ and ‘M’ denoting the number of nodes and edges in the graph, respectively.

Each of the next ‘M’ lines contains three space integers ‘U’, ‘V’, and ‘W’. There is an undirected edge between node ‘U’ and ‘V’ of weight ‘W’.

Output Format:

For each test case, return the weight of the minimum spanning tree of the given graph.

Note:

You don't have to print the expected output, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 10000
1 <= M <= 10000
1 <= W <= 1000
1 <= U, V <= N

Time limit: 1 sec