// Arup Guha
// 4/28/2020
// Alternate solution to 2020 FHSPS Problem: Roads? Where We Are Going We Don't Need Roads.

import java.util.*;

public class roads_arup {

	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process all cases.
		for (int loop=0; loop<nC; loop++) {
		
			// Read in # vertices, edges.
			int n = stdin.nextInt();
			int e = stdin.nextInt();
			edge[] list = new edge[e];
			
			// Read in the edges.
			for (int i=0; i<e; i++) {
				int u = stdin.nextInt()-1;
				int v = stdin.nextInt()-1;
				int w = stdin.nextInt();
				list[i] = new edge(u,v,w);
			}
			
			// Sort edges for Kruskal's, set up disjoing set.
			Arrays.sort(list);
			djset dj = new djset(n);
			int mst = 0, taken = 0;
			
			// Keep going till we have enough edges.
			for (int i=0; i<e && taken < n-1; i++) {
				
				// Add if we need to.
				if (dj.union(list[i].u, list[i].v)) {
					mst += list[i].w;
					taken++;
				}
			}
			
			// Ta da!
			System.out.println(mst);
		}
	}

}

class edge implements Comparable<edge> {

	public int u;
	public int v;
	public int w;
	
	public edge(int myu, int myv, int myw) {
		u = myu;
		v = myv;
		w = myw;
	}
	
	public int compareTo(edge other) {
	
		// even goes before odd...
		if (w%2 == 0 && other.w%2 != 0) return -1;
		if (w%2 != 0 && other.w%2 == 0) return 1;
		
		// sorts from biggest to smallest.
		return other.w - this.w;
	}

}

class djset {

	public int n;
	public int[] par;
	
	// Sets up the object.
	public djset(int myn) {
		n = myn;
		par = new int[n];
		for (int i=0; i<n; i++) par[i] = i;
	}
	
	// Returns the root of the tree with v, using path compression.
	public int find(int v) {
		if (par[v] == v) return v;
		return par[v] = find(par[v]);
	}
	
	// Puts together the set of u and v. Returns false is already together and takes no action.
	// Returns true if union is completed.
	public boolean union(int u, int v) {
		
		// Get roots.
		int rootu = find(u);
		int rootv = find(v);
		
		// Already together.
		if (rootu == rootv) return false;
		
		// Merge and return success.
		par[rootv] = rootu; 
		return true;
	}

}