#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll INF=1e18;
int t,n,k,u,v,w,h[N],tot;
ll ans;
struct edge
{
	int to,val,nxt;
}e[N<<1];
void add(int u,int v,int w) 
{
	e[++tot]={v,w,h[u]};
	h[u]=tot;
}
struct node
{
	priority_queue<ll,vector<ll>,greater<ll>> ql;
	priority_queue<ll> qr;
	ll cl,cr;
	int sz;
	void clear() 
	{
		while(ql.size()) ql.pop();
		while(qr.size()) qr.pop();
		cl=cr=0;sz=0;	
	} 
	void insert(ll x)
	{
		ql.push(x-cl);sz++;
		if((int)ql.size()>k/2)
		{
			qr.push(ql.top()+cl-cr);
			ql.pop();
		}
	}
	void sswap(node &b)
	{
		swap(ql,b.ql);swap(qr,b.qr);
		swap(cl,b.cl);swap(cr,b.cr);swap(sz,b.sz);
	}
	ll sum(int k) 
	{
		ll res=0;
		while(k--)
		{
			if(ql.size()) res+=ql.top()+cl,ql.pop();
			else res+=qr.top()+cr,qr.pop(); 
		}
		return res;
	}
	void out()
	{
		vector<int> v;
		while(ql.size()) v.push_back(ql.top()),ql.pop();
		reverse(begin(v),end(v));
		for(int u:v) ql.push(u),cout<<u+cl<<" ";
		v.clear();
		while(qr.size()) v.push_back(qr.top()),qr.pop(); 
		for(int u:v) qr.push(u),cout<<u+cr<<" ";
		cout<<"\n";
	}
}f[N];
void merge(node &a,node &b)
{
	if(a.sz<b.sz) a.sswap(b);
	while(b.ql.size()) a.insert(b.ql.top()+b.cl),b.ql.pop();
	while(b.qr.size()) a.insert(b.qr.top()+b.cr),b.qr.pop();
}
void dfs(int u,int fa) 
{
	f[u].insert(0);
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to,w=e[i].val;
		if(v==fa) continue;
		dfs(v,u);f[v].cl+=w;f[v].cr-=w;
		if(f[v].qr.size()) 
		{
			ll t=f[v].qr.top();f[v].qr.pop();
			f[v].qr.push(t+w);	
		}  
		merge(f[u],f[v]);
	}
}
int main() 
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);tot=0;ans=0;
		for(int i=1;i<=n;i++) h[i]=0,f[i].clear();
		for(int i=1;i<n;i++) 
		{
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w),add(v,u,w);
		}
		dfs(1,0);ans=2*f[1].sum(k);
		printf("%lld\n",ans);
	}
	return 0;
}