// author : black_trees

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

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n, k;

struct Convex {
	int sum = 0;
	std::priority_queue<int, vector<int>, greater<int>> slope;
	void Merge(Convex rhs) {
		sum += rhs.sum;
		while((int)rhs.slope.size())
			slope.push(rhs.slope.top()), rhs.slope.pop(); 
		while((int)slope.size() > k)
			sum -= slope.top(), slope.pop();
	}
	void Add(int u, int v) {
		int ret = 0;
		std::priority_queue<int, vector<int>, greater<int>> q;
		while((int)slope.size()) {
			int x = slope.top();
			slope.pop();
			int idx = (int)slope.size(), val = 0;
			if(idx * 2 < v) val = (idx + 1) * 2 <= v ? x + u : x;
			else val = x - u;
			q.push(val), ret += val;
		}
		slope = q, sum = ret;
	}
};

int tot = 0, head[si];
struct Edge { int ver, Next, w; } e[si << 1];
inline void add(int u, int v, int w) { e[tot] = (Edge){v, head[u], w}, head[u] = tot++; }

int ans = -1;
Convex dfs(int u, int fa) {
	Convex a; a.slope.push(0);
	for(int i = head[u]; ~i; i = e[i].Next) {
		int v = e[i].ver, w = e[i].w;
		if(v == fa) continue;
		Convex b = dfs(v, u);
		b.Add(2 * w, k);
		if((int)a.slope.size() > (int)b.slope.size())
			a.Merge(b);
		else b.Merge(a), swap(a, b);
	}
	ans = max(ans, a.sum); 
	return a;
}

signed main() {

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

int T; cin >> T;
while(T--) {
	cin >> n >> k;
	tot = 0, ans = -1;
	for(int i = 0; i <= n; ++i)
		head[i] = -1;
	for(int i = 1; i < n; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	dfs(1, 0);
	cout << ans << endl;
}

	return 0;
}