// Arup Guha
// 10/28/2018
// Solution to 2013 Pac NW Problem D: Delta Quadrant

import java.util.*;
public class d {
	
	public static int n;
	public static int k;
	public static vertex[] g;
	public static long totalCost;
	public static long[][] memo;
	public static int[] preToID;
	
	public static int id;
	
	public static void main(String[] args) {
		
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process each case.
		for (int loop=0; loop<nC; loop++) {
			
			// Set up basic graph.
			n = stdin.nextInt();
			k = stdin.nextInt();
			g = new vertex[n];
			for (int i=0; i<n; i++)
				g[i] = new vertex(i);
			
			// Now, add edges.
			totalCost = 0;
			for (int i=0; i<n-1; i++) {
				int u = stdin.nextInt();
				int v = stdin.nextInt();
				long w = stdin.nextLong();
				g[u].kids.add(new edge(v,w));
				g[v].kids.add(new edge(u,w));
				totalCost += w;
			}
			
			// Ta da!
			System.out.println(solve());
		}
	}
	
	public static long solve() {

		// Gotta trace the whole tree (twice).
		if (k == 0) return 2*totalCost;
		
		long best = 0;
		
		// Guaranteed to get the best answer from at least 1
		// of k+1 possible starting vertices.
		for (int i=0; i<k+1; i++) 
			best = Math.max(best, go(i));
		
		// This is what we want.
		return 2*totalCost - 2*best;
	}
	
	public static long go(int i) {
		
		// Probably don't need this but just being safe.
		for (int loop=0; loop<n; loop++)
			g[i].reset();

		// Set up pre/post labels and tree costs.
		id = 0;
		preToID = new int[n];
		label(i, -1, 0);
		
		// Set up memo array.
		memo = new long[n][k+1];
		for (int loop=0; loop<n; loop++) Arrays.fill(memo[loop], -1);
		
		// Go.
		return gorec(0,0);
	}
	
	// Returns the best result if we're at preorder ID loc and we've already
	// skipped skip # of vertices.
	public static long gorec(int loc, int skip) {
		
		// Some base cases.
		if (loc >= n) return 0;
		if (skip > k) return Long.MIN_VALUE;
		if (memo[loc][skip] != -1) return memo[loc][skip];
		
		// Skip nothing.
		long cur = gorec(loc+1, skip);
		
		// If we were to skip this subtree...
		int newskip = g[preToID[loc]].post - g[preToID[loc]].pre + 1 + skip;
		
		// As long as we aren't skipping too many try this way.
		if (newskip <= k)
			cur = Math.max(cur, g[preToID[loc]].cost + gorec(g[preToID[loc]].post+1,newskip));
		
		// Store and return.
		memo[loc][skip] = cur;
		return cur;
	}
	
	public static void label(int i, int mypar, long parcost) {
		
		// Set pre label and parent.
		g[i].par = mypar;
		preToID[id] = i;
		g[i].pre = id++;
		g[i].cost = parcost;
		
		// Recurse through kids.
		for (edge e: g[i].kids) {
			
			// Skip the parent.
			if (e.to == g[i].par) continue;
			
			// Recurse here.
			label(e.to, i, e.w);
			
			// We add the edge down to the kid and the kids total cost.
			g[i].cost += g[e.to].cost;
		}
		
		// Now we can do the post label.
		g[i].post = id-1;
	}
}

class vertex {
	
	public int id;
	public int par;
	public int pre;
	public int post;
	public long cost;
	public ArrayList<edge> kids;
	
	public vertex(int myid) {
		id = myid;
		par = -1;
		pre = -1;
		post = -1;
		kids = new ArrayList<edge>();
		cost = 0;
	}
	
	public void reset() {
		par = -1;
		pre = -1;
		post = -1;
	}
}

class edge {
	
	public int to;
	public long w;
	
	public edge(int v, long myw) {
		to = v;
		w = myw;
	}
}