#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200020
int n,k;
struct seg{
	priority_queue<ll> q;
	ll tag;
	void merge(seg &x){
		if(x.q.size()>q.size())swap(q,x.q),swap(x.tag,tag);
		while(x.q.size())q.push(x.q.top()+x.tag-tag),x.q.pop();
	}
	void clear(){while(q.size())q.pop();tag=0;}
};
struct conv{
	seg s1,s2,s3;
	void clear(){s1.clear(),s2.clear(),s3.clear();}
	void maintain(){
		while(s1.q.size()>k/2)s2.q.push(s1.q.top()),s1.q.pop();
		while(s2.q.size()>k%2)s3.q.push(s2.q.top()),s2.q.pop();
	}
	void merge(conv &x){
		s1.merge(x.s1),s2.merge(x.s2),s3.merge(x.s3);
	}
}d[N];
struct edge{
	int v,w,nxt;
}e[N<<1];
int head[N],tot=1;
void ae(int u,int v,int w){e[tot]=(edge){v,w,head[u]};head[u]=tot++;}
void dfs(int u,int f){
	d[u].s1.q.push(-d[u].s1.tag);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;if(v==f)continue;
		dfs(v,u);
		d[v].s1.tag+=w*2;d[v].s3.tag-=w*2;
		d[u].merge(d[v]);
	}
	d[u].maintain();
}
void work(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		ae(u,v,w),ae(v,u,w);
	}
	dfs(1,0);
	vector<ll> v;
	while(d[1].s3.q.size())v.push_back(d[1].s3.q.top()+d[1].s3.tag),d[1].s3.q.pop();
	while(d[1].s2.q.size())v.push_back(d[1].s2.q.top()+d[1].s2.tag),d[1].s2.q.pop();
	while(d[1].s1.q.size())v.push_back(d[1].s1.q.top()+d[1].s1.tag),d[1].s1.q.pop();
	reverse(v.begin(),v.end());
	ll ans=0;
	for(int i=0;i<=k+1;i++)ans+=v[i];
	printf("%lld\n",ans);
	for(int i=1;i<=n;i++)d[i].clear();
	memset(head,0,sizeof(head));tot=1;
}
int main(){
	int t;scanf("%d",&t);
	while(t--)work();
	return 0;
}