#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
vector<pair<int,lld> >nei[1000000];
lld dist[1000000];
bool vis[1000000];
int lab[1000000];
int n,k;
void DFS(int node, lld d=0, int label=-1){
	dist[node]=d;
	vis[node]=true;
	lab[node]=label;
	trav(a,nei[node]){
		if(!vis[a.first]){
			if(label==-1)DFS(a.first,d+a.second,a.first);
			else DFS(a.first,d+a.second,label);
		}
	}
}
void st(int node){
	rep(i,0,n)vis[i]=false;
	DFS(node);
}
void reset(){
	rep(i,0,n)vis[i]=false;
}
int sz[1000000];
bool bl[1000000];
void getsz(int node){
	vis[node]=true;
	sz[node]=1;
	trav(a,nei[node]){
		if(!vis[a.first] && !bl[a.first]){
			getsz(a.first);
			sz[node]+=sz[a.first];
		}
	}
}
int getcent(int node, int treesz){
	trav(a,nei[node]){
		if(!bl[a.first] && sz[node]>sz[a.first] && sz[a.first]*2>treesz){
			return getcent(a.first,treesz);
		}
	}
	return node;
}
int cnt[1000000];
vector<pair<lld,int> >V;
int exc;
lld test(int node){
	exc=-1;
	st(node);
	V.clear();
	rep(i,0,n)cnt[i]=0;
	rep(i,0,n){
		V.push_back({-dist[i],lab[i]});
	}
	sort(V.begin(),V.end());
	int tot=0;
	lld ans=0;
	trav(a,V){
		if(tot==k)continue;
		lld D=-a.first;
		int v=a.second;
		if(2*(cnt[v]+1)<=k){
			cnt[v]++;
			tot++;
			ans+=2*D;
		}else{
			exc=v;
		}
	}
	return ans;
}
void solve(){
	cin>>n>>k;
	rep(i,0,n)nei[i].clear(),vis[i]=false,bl[i]=false;
	rep(i,0,n-1){
		int x,y;
		lld c;
		cin>>x>>y>>c;
		x--;y--;
		nei[x].push_back({y,c});
		nei[y].push_back({x,c});
	}
	lld ans=0;
	int ver=0;
	while(true){
		reset();
		getsz(ver);
		int S=sz[ver];
		if(S<=5)break;
		int cen=getcent(ver,S);
		ans=max(ans,test(cen));
		if(exc==-1){
			cout<<ans<<"\n";
			return;
		}
		bl[cen]=true;
		ver=exc;
	}
	rep(i,0,n){
		if(vis[i])ans=max(ans,test(i));
	}
	cout<<ans<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	cin>>tt;
	while(tt--){
		solve();
	}
}