#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
	int s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
template<const int N,const int M>
struct wgraph
{
	int head[N+5];
	int ww[M+5];
	int t[M+5];
	int x[M+5];
	int cntm;
	wgraph(){ cntm=1;}
	inline void clear(int n=N)
	{
		cntm=1;
		for(int i=1;i<=n;i++) head[i]=0;
	}
	inline void ad(int u,int v,int w)
	{
		cntm++;
		t[cntm]=v;
		x[cntm]=head[u];
		ww[cntm]=w;
		head[u]=cntm;
	}
	inline void add(int u,int v,int w)
	{
		ad(u,v,w);
		ad(v,u,w);
	}
	inline int st(int num){ return head[num];}
	inline int to(int num){ return t[num];}
	inline int nx(int num){ return x[num];}
	inline int w(int num){ return ww[num];}
};
wgraph<200000,400000>g;
vc<int>nod[200001];
int anc[200001];
int d1[200001];
int fa[200001];
ll d2[200001];
int id[200001];
int c[200001];
int n,k;
void dfs(int num)
{
	if(!fa[num]) anc[num]=0;
	else if(!anc[fa[num]]) anc[num]=num;
	else anc[num]=anc[fa[num]];
	nod[d1[num]].push_back(num),c[num]=0;
	for(int i=g.st(num);i;i=g.nx(i))
	{
		int p=g.to(i);
		if(p==fa[num]) continue;
		fa[p]=num,d1[p]=d1[num]+1;
		d2[p]=d2[num]+g.w(i);
		dfs(p);
	}
}
inline void cover(int u)
{
	for(int i=0;i<=n;i++) id[i]=i,nod[i].clear();
	d1[u]=0,fa[u]=0,d2[u]=0,dfs(u);
	sort(id+1,id+n+1,[](int x,int y)
	{
		if(d2[x]!=d2[y]) return d2[x]>d2[y];
		return x<y;
	});
	for(int i=1;i<=k;i++) c[id[i]]++;
	for(int i=n-1;i;i--) for(int p:nod[i]) c[fa[p]]+=c[p];
}
inline ll run(int u)
{
	d1[u]=0,d2[u]=0,fa[u]=0,c[0]=0,dfs(u);
	sort(id+1,id+n+1,[](int x,int y)
	{
		if(d2[x]!=d2[y]) return d2[x]>d2[y];
		return x<y;
	});
	int now=0;ll ans=0;
	for(int i=1;i<=n&&now<k;i++)
	{
		int p=id[i];
		if((c[anc[p]]+1)*2>k) continue;
		// printf("%d : anc=%d\n",p,anc[p]);
		c[anc[p]]++,ans+=d2[p],now++;
	}
	if(now!=k) return -1;
	// printf("run %d : %lld\n",u,ans<<1);
	return ans<<1;
}
int main()
{
	int T=read();
	while(T--)
	{
		g.clear(n),n=read(),k=read();
		for(int i=1;i<n;i++)
		{
			int u=read(),v=read(),w=read();
			g.add(u,v,w);
		}
		cover(1);int o=-1;
		for(int i=0;i<=n;i++) for(int j:nod[i]) if(c[j]*2>k) o=j;
		assert(o!=-1);

		vc<int>val;
		for(int i=o;i;i=fa[i]) val.push_back(i);
		int l=0,r=(int)val.size()-1;
		while(r-l>1)
		{
			int mid=(l+r)>>1;cover(val[mid]);
			int L=c[val[mid-1]],R=c[val[mid+1]];
			if(L*2<=k) l=mid;
			if(R*2<=k) r=mid;
		}
		ll ans=run(val[l]);
		if(l!=r) ans=max(ans,run(val[r]));
		printf("%lld\n",ans);
	}
	return 0;
}