#include <iostream>
#include <cstdio>
#include <random>
#define ll long long
using namespace std;
mt19937 rnd(12345678);
struct node{
	int l,r,sz;
	ll val,tag;
	int key;
	void clear(){
		l=r=sz=val=tag=key=0;
		return;
	}
}fhq[200005];
node make_node(ll val){
	node ans;
	ans.l=ans.r=0,ans.sz=1;
	ans.val=val,ans.tag=0;
	ans.key=rnd()%1000000000+1;
	return ans;
}
void pushdown(int now){
	if (fhq[now].l)fhq[fhq[now].l].val+=fhq[now].tag,fhq[fhq[now].l].tag+=fhq[now].tag;
	if (fhq[now].r)fhq[fhq[now].r].val+=fhq[now].tag,fhq[fhq[now].r].tag+=fhq[now].tag;
	fhq[now].tag=0;
	return;
}
void pushup(int now){
	fhq[now].sz=1;
	if (fhq[now].l)fhq[now].sz+=fhq[fhq[now].l].sz;
	if (fhq[now].r)fhq[now].sz+=fhq[fhq[now].r].sz;
	return; 
}
void split1(int now,int k,int &x,int &y){
	if (now==0){
		x=y=0;
		return;
	}
	pushdown(now);
	if (fhq[fhq[now].l].sz+1<=k){
		x=now;
		split1(fhq[now].r,k-(fhq[fhq[now].l].sz+1),fhq[now].r,y);
	}
	else{
		y=now;
		split1(fhq[now].l,k,x,fhq[now].l);
	}
	pushup(now);
	return;
}
void split2(int now,int k,int &x,int &y){
	if (now==0){
		x=y=0;
		return;
	}
	pushdown(now);
	if (fhq[now].val>=k){
		x=now;
		split2(fhq[now].r,k,fhq[now].r,y);
	}
	else{
		y=now;
		split2(fhq[now].l,k,x,fhq[now].l);
	}
	pushup(now);
	return;
}
int merge(int x,int y){
	if (x==0)return y;
	if (y==0)return x;
	pushdown(x),pushdown(y);
	if (fhq[x].key>=fhq[y].key){
		fhq[x].r=merge(fhq[x].r,y);
		pushup(x);
		return x;
	}
	else{
		fhq[y].l=merge(x,fhq[y].l);
		pushup(y);
		return y;
	}
	return 0; 
}
int cnt;
int t,n,k;
int u[400005],v[400005],w[400005],first[200005],nxt[400005];
int root[200005];
int tot,id[200005];
void get_id(int now){
	if (now==0)return;
	pushdown(now);
	if (fhq[now].l)get_id(fhq[now].l);
	id[++tot]=now;
	if (fhq[now].r)get_id(fhq[now].r);
	return;
}
void ins(int &a,int b){
	int x,y;
	split2(a,fhq[b].val,x,y);
	a=merge(merge(x,b),y);
	return;
}
void dfs(int now,int fa,int l){
	root[now]=++cnt;
	fhq[root[now]]=make_node(0);
	for (int i=first[now];i;i=nxt[i])
		if (v[i]!=fa){
			dfs(v[i],now,w[i]);
			if (fhq[root[now]].sz<fhq[root[v[i]]].sz)swap(root[now],root[v[i]]);
			tot=0;
			get_id(root[v[i]]);
			for (int i=1;i<=tot;i++)fhq[id[i]].l=fhq[id[i]].r=0,fhq[id[i]].sz=1;
			for (int i=1;i<=tot;i++)ins(root[now],id[i]);
		}
	if (fhq[root[now]].sz>k){
		int x,y;
		split1(root[now],k,x,y);
		root[now]=x;
	}
	if (k%2==0){
		int x,y;
		split1(root[now],k/2,x,y);
		if (x!=0)fhq[x].val+=l,fhq[x].tag+=l;
		if (y!=0)fhq[y].val-=l,fhq[y].tag-=l;
		root[now]=merge(x,y);
	}
	if (k%2==1){
		int x,y,z;
		split1(root[now],k/2,x,y);
		split1(y,1,y,z);
		if (x!=0)fhq[x].val+=l,fhq[x].tag+=l;
		if (z!=0)fhq[z].val-=l,fhq[z].tag-=l;
		root[now]=merge(merge(x,y),z);
	}
	return;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		for (int i=1;i<n;i++){
			scanf("%d%d%d",&u[i],&v[i],&w[i]);
			nxt[i]=first[u[i]],first[u[i]]=i;
			u[i+n]=v[i],v[i+n]=u[i],w[i+n]=w[i];
			nxt[i+n]=first[u[i+n]],first[u[i+n]]=i+n;
		}
		dfs(1,0,0);
		tot=0;
		get_id(root[1]);
		ll sum=0;
		for (int i=1;i<=tot;i++)sum+=fhq[id[i]].val; 
		printf("%lld\n",2*sum);
		while(cnt>0)fhq[cnt].clear(),cnt--;
		for (int i=1;i<=n;i++)first[i]=0;
	}
	return 0;
}