import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Roads {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int runs = scan.nextInt();
		
		for (int i=0; i<runs; i++) {
			ArrayList<Road> pq = new ArrayList<Road>();
			int ans = 0;
			
			int c = scan.nextInt();
			int r = scan.nextInt();
			
			ArrayList<Road>[] cityRoads = new ArrayList[c+1];
			boolean visited[] = new boolean[c+1];
			
			for (int j=0; j<c+1; j++) {
				cityRoads[j] = new ArrayList<Road>();
				visited[j] = false;
			}
			
			for (int j=0; j<r; j++) {
				int city1 = scan.nextInt();
				int city2 = scan.nextInt();
				int priority = scan.nextInt(); 
				cityRoads[city1].add(new Road(priority, city2));
				cityRoads[city2].add(new Road(priority, city1));

			}
			
			
					
			visited[1] = true;
			pq.addAll(cityRoads[1]);
			Collections.sort(pq);
			
			
			while (!pq.isEmpty()) {
				Road temp = pq.remove(0);
				if (visited[temp.toCity]) {
					continue;
				}
				
				visited[temp.toCity] = true;
				ans += temp.score;
				pq.addAll(cityRoads[temp.toCity]);
				Collections.sort(pq);
				
			}

			System.out.println(ans);
		}
		
		
	}

}

class Road implements Comparable<Road> {

	public int score;
	public int toCity;
	
	public Road (int s, int c) {
		score = s;
		toCity = c;
	}
	
	@Override
	public int compareTo(Road r) {
		if (score %2==0 && r.score%2 == 1) {
			return -1;
		} else if (r.score%2==0 && score%2 == 1) {
			return 1;
		} else {
			return r.score - this.score;
		}
	}
	
	public String toString() {
		return ""+score;
	}
	
}