// author : black_trees

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n, k;
int l[si], r[si];
std::vector<std::pair<int, int>> G[si];
std::priority_queue<int> pq_l[si], pq_r[si];

void Merge(std::priority_queue<int> &a, 
		   std::priority_queue<int> &b, int &x, int &y) {
	if(a.size() < b.size()) swap(a, b), swap(x, y);
	for(; !b.empty(); b.pop()) a.push(b.top() + y - x);
}

void dfs(int u, int fa) {
	pq_l[u].push(0);
	for(auto &[v, w]: G[u]) {
		if(v == fa) continue;
		dfs(v, u), l[v] -= w; r[v] -= w;
		if(k & 1 && !pq_r[v].empty()){
			int t = pq_r[v].top(); 
			pq_r[v].pop(), pq_r[v].push(t + w);
		}
		Merge(pq_l[u], pq_l[v], l[u], l[v]);
		for(; pq_l[u].size() > (k / 2); pq_l[u].pop())
			pq_r[u].push(-l[u] - pq_l[u].top() - r[u]);
		Merge(pq_r[u], pq_r[v], r[u], r[v]);
	}
}

int main() {

	cin.tie(0) -> sync_with_stdio(false);
	cin.exceptions(cin.failbit | cin.badbit);

	int T; cin >> T;
	while(T--) {
		cin >> n >> k;
		for(int i = 1; i <= n; ++i)
			G[i].clear(), l[i] = r[i] = 0;
		for(int i = 1; i <= n - 1; ++i) {
			int u, v, w;
			cin >> u >> v >> w;
			G[u].push_back(make_pair(v, w));
			G[v].push_back(make_pair(u, w));
		}
		dfs(1, 0); 
		int ans = 0, i = 0;
		for(i = 0; !pq_l[1].empty(); ++i)
			ans -= pq_l[1].top() + l[1], pq_l[1].pop();
		for(; !pq_r[1].empty(); ++i) {
			if(i < k) 
				ans += pq_r[1].top() + r[1]; 
			pq_r[1].pop();
		}
		cout << ans * 2 << endl;
	}
	
	return 0;
}