#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000

#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const ll mod = 998244353;

priority_queue<ll,vector<ll>,greater<ll>>up[200005], mid[200005], dw[200005];
ll lazyup[200005],lazymid[200005],lazydw[200005];

int n,k;
vector<P>edge[200005];
void look(priority_queue<ll,vector<ll>,greater<ll>>&que,ll x){
    vector<ll>vec;
    while(que.size()){ vec.pb(que.top()); que.pop(); }
    reverse(vec.begin(),vec.end());
    for(auto v:vec) cout << v+x << " ";
    cout << endl;
    for(auto v:vec) que.push(v);
}
void dfs(int v,int u){
	P mx = mp(0,0);
	rep(i,edge[v].size()){
		if(edge[v][i].fi == u) continue;
		dfs(edge[v][i].fi,v);
		if(mx < mp((int)(up[edge[v][i].fi].size() + mid[edge[v][i].fi].size() + dw[edge[v][i].fi].size()), edge[v][i].fi)){
			mx = mp((int)(up[edge[v][i].fi].size() + mid[edge[v][i].fi].size() + dw[edge[v][i].fi].size()), edge[v][i].fi);
		}
	}
	if(mx.sc == 0){
		up[v].push(0);
		return;
	}
	else{
		swap(up[v],up[mx.sc]);
		swap(mid[v],mid[mx.sc]);
		swap(dw[v],dw[mx.sc]);
		lazyup[v] = lazyup[mx.sc];
		lazymid[v] = lazymid[mx.sc];
		lazydw[v] = lazydw[mx.sc];
	}
	rep(i,edge[v].size()){
	    if(edge[v][i].fi == mx.sc){
	        lazyup[v] += 2 * edge[v][i].sc;
	        lazydw[v] -= 2 * edge[v][i].sc;
	        break;
	    }
	}
	rep(i,edge[v].size()){
		if(edge[v][i].fi == u) continue;
		if(edge[v][i].fi == mx.sc) continue;
		while(up[edge[v][i].fi].size()){
			ll x = up[edge[v][i].fi].top() + lazyup[edge[v][i].fi] + 2 * edge[v][i].sc;
			up[v].push(x - lazyup[v]);
			up[edge[v][i].fi].pop();
		}
		while(mid[edge[v][i].fi].size()){
			ll x = mid[edge[v][i].fi].top() + lazymid[edge[v][i].fi];
			up[v].push(x - lazyup[v]);
			mid[edge[v][i].fi].pop();
		}
		while(dw[edge[v][i].fi].size()){
			ll x = dw[edge[v][i].fi].top() + lazydw[edge[v][i].fi] - 2 * edge[v][i].sc;
			up[v].push(x - lazyup[v]);
			dw[edge[v][i].fi].pop();
		}
	}
	up[v].push(-lazyup[v]);
	while(up[v].size() > k/2){
		ll x = up[v].top() + lazyup[v]; up[v].pop();
		mid[v].push(x - lazymid[v]);
	}
	while(mid[v].size() > k%2){
		ll x = mid[v].top() + lazymid[v]; mid[v].pop();
		dw[v].push(x - lazydw[v]);
	}
	//cout << v << "_______" << endl;
	//look(up[v],lazyup[v]);
	//look(mid[v],lazymid[v]);
	//look(dw[v],lazydw[v]);
}
void solve(){
    scanf("%d%d",&n,&k);
    repn(i,n){
        while(up[i].size()) up[i].pop();
        while(mid[i].size()) mid[i].pop();
        while(dw[i].size()) dw[i].pop();
        edge[i].clear();
        lazyup[i] = lazymid[i] = lazydw[i] = 0;
    }
    rep(i,n-1){
    	int a,b,c;
    	scanf("%d%d%d",&a,&b,&c);
    	edge[a].pb(mp(b,c));
    	edge[b].pb(mp(a,c));
    }
    if(k == 1){
    	puts("0");
    	return ;
    }
    dfs(1,-1);
    ll ans = 0;
    int use = 0;
    vector<ll>vec;
    while(up[1].size()){ vec.pb(up[1].top() + lazyup[1]); up[1].pop(); use++; }
    while(mid[1].size()){ vec.pb(mid[1].top() + lazymid[1]); mid[1].pop(); use++; }
    while(dw[1].size()){ vec.pb(dw[1].top() + lazydw[1]); dw[1].pop(); use++; }
    sort(vec.begin(),vec.end(),greater<ll>());
    rep(i,k) ans += vec[i];
	//assert(use == k);
	printf("%lld\n",ans);
}
int main(){
	int t; scanf("%d",&t);
	while(t--) solve();
}