#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<random>
#define N 300000
using namespace std;
mt19937 RAND(random_device{}());
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data;
};
int Ts,n,k,rt[N+1],tfa[N+1],sz[N+1],leng;
long long tong[N+1],ans;
bool used[N+1];
vector<reads>E[N+1];
void add(int x,int y,int z)
{
	E[x].push_back((reads){y,z}),E[y].push_back((reads){x,z});
	return;
}
struct fhq_treap
{
	struct node
	{
		int ls,rs,sz;
		long long data,lazy;
		int rd;
	};
	node tree[N+1];
	int length,dque[N+1],top;
	int new_node(long long x)
	{
		int nw;
		if (top) nw=dque[top--];
		else nw=++length;
		tree[nw]=(node){0,0,1,x,0,(int)(RAND()%inf)};
		return nw;
	}
	void push_up(int k)
	{
		tree[k].sz=tree[tree[k].ls].sz+tree[tree[k].rs].sz+1;
		return;
	}
	void spread(int k)
	{
	    if (tree[k].ls) tree[tree[k].ls].data+=tree[k].lazy,tree[tree[k].ls].lazy+=tree[k].lazy;
		if (tree[k].rs) tree[tree[k].rs].data+=tree[k].lazy,tree[tree[k].rs].lazy+=tree[k].lazy;
		tree[k].lazy=0;
		return;
	}
	int merge(int x,int y)
	{
		if (!x||!y) return x^y;
		spread(x),spread(y);
		if (tree[x].rd<tree[y].rd)
		{
			tree[x].rs=merge(tree[x].rs,y),push_up(x);
			return x;
		}
		else
		{
			tree[y].ls=merge(x,tree[y].ls),push_up(y);
			return y;
		}
	}
	void split(int k,int d,int &x,int &y)
	{
		if (!k)
		{
			x=y=0;
			return;
		}
		spread(k);
		if (d<=tree[tree[k].ls].sz) split(tree[k].ls,d,x,tree[k].ls),y=k;
		else split(tree[k].rs,d-tree[tree[k].ls].sz-1,tree[k].rs,y),x=k;
		push_up(k);
		return;
	}
	void split2(int k,int d,int &x,int &y)
	{
		if (!k)
		{
			x=y=0;
			return;
		}
		spread(k);
		if (d>tree[k].data) split2(tree[k].ls,d,x,tree[k].ls),y=k;
		else split2(tree[k].rs,d,tree[k].rs,y),x=k;
		push_up(k);
		return;
	}
	void solve(int k)
	{
		spread(k);
		if (tree[k].ls) solve(tree[k].ls);
		if (tree[k].rs) solve(tree[k].rs);
		tong[++leng]=tree[k].data,dque[++top]=k;
		return;	
	}
};
fhq_treap T;
void merge(int x,int y)
{
	int A,B;
	if (T.tree[rt[x]].sz>T.tree[rt[y]].sz) swap(rt[x],rt[y]);
	leng=0,T.solve(rt[x]);
	for (int i=1;i<=leng;++i) T.split2(rt[y],tong[i],A,B),rt[y]=T.merge(T.merge(A,T.new_node(tong[i])),B);
	if (T.tree[rt[y]].sz>k) T.split(rt[y],k,A,B),rt[y]=A;
	return;
}
void dfs(int x)
{
	int A,B;
	used[x]=sz[x]=1,rt[x]=T.new_node(0);
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i].num])
			tfa[E[x][i].num]=E[x][i].data,dfs(E[x][i].num),merge(E[x][i].num,x);
	if (x!=1)
	{
		T.split(rt[x],k>>1,A,B),T.tree[A].data+=(tfa[x]<<1),T.tree[A].lazy+=(tfa[x]<<1),rt[x]=T.merge(A,B);
		T.split(rt[x],(k+1)>>1,A,B),T.tree[B].data-=(tfa[x]<<1),T.tree[B].lazy-=(tfa[x]<<1),rt[x]=T.merge(A,B);
	}
	return;
}
int main()
{
	int x,y,z;
	Ts=read();
	while (Ts--)
	{
		n=read(),k=read(),T.length=T.top=ans=0;
		for (int i=1;i<=n;++i) used[i]=0;
		for (int i=1;i<=n-1;++i) x=read(),y=read(),z=read(),add(x,y,z);
		dfs(1),leng=0,T.solve(rt[1]);
		for (int i=1;i<=leng;++i) ans+=tong[i];
		printf("%lld\n",ans);
	}
	return 0;
}