#include <cstdio>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=200005;
int n,K;
vector<pii> edge[N];
bool vis[N];
int _,siz[N];
void dfs_c(int x,int p,int S){
	siz[x]=1;
	int mx=0;
	for(auto &[y,w]:edge[x]){
		if(y==p || vis[y])
			continue;
		dfs_c(y,x,S);
		siz[x]+=siz[y];
		if(mx<siz[y])
			mx=siz[y];
	}
	if(mx<S-siz[x])
		mx=S-siz[x];
	if(mx*2<=S)
		_=x;
}
vector<tuple<ll,int,int>> v;
void dfs_t(int x,int p,ll d,int c){
	v.push_back({d,c,x});
	for(auto &[y,w]:edge[x]){
		if(y==p)
			continue;
		dfs_t(y,x,d+w,c);
	}
}
int cnt[N];
ll mx;
int rt;
bool cur[N],b[N];
void Solve(int x,int S){
	dfs_c(x,0,S),vis[x=_]=true,dfs_c(x,0,S);
	v.clear();
	v.push_back({0,x,x});
	for(auto &[y,w]:edge[x])
		dfs_t(y,x,w,y);
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	fill_n(cnt+1,n,0);
	fill_n(cur+1,n,false);
	ll s=0;
	int t=0;
	int nx=0;
	for(auto &[d,c,x]:v){
		if((cnt[c]+1)*2<=K){
			s+=d,++t;
			++cnt[c];
			cur[x]=true;
			if(t==K)
				break;
		}else if(!nx){
			nx=c;
		}
	}
	if(t==K && mx<s){
		rt=x,mx=s;
		copy_n(cur+1,n,b+1);
	}
	if(nx && !vis[nx])
		Solve(nx,siz[nx]);
}
pair<ll,int> dfs(int x,int p){
	ll mx=0;
	int siz=b[x];
	for(auto &[y,w]:edge[x]){
		if(y==p)
			continue;
		auto t=dfs(y,x);
		if((t.second+1)*2<=K)
			t.first+=w;
		if(mx<t.first)
			mx=t.first;
		siz+=t.second;
	}
	if(b[x])
		mx=0xc0c0c0c0c0c0c0c0;
	return {mx,siz};
}
void Main(){
	scanf("%d%d",&n,&K);
	mx=-1,rt=0;
	for(int i=1;i<=n;++i){
		vis[i]=false;
		edge[i].clear();
	}
	for(int i=1,u,v,w;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		edge[u].emplace_back(v,w);
		edge[v].emplace_back(u,w);
	}
	if(K&1){
		--K;
		Solve(1,n);
		mx+=dfs(rt,0).first;
	}else{
		Solve(1,n);
	}
	printf("%lld\n",mx*2);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)
		Main();
	return 0;
}