#include<iostream>
#include<vector>
#include<algorithm>
 #include<cassert>
using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#pragma GCC optimize("-O3","unroll-loops")
#pragma GCC optimize("-Ofast")
vector<vector<pair<int,lld> > >nei;
lld dist[1000000];
bool vis[1000000];
int lab[1000000];
int n,k;
void DFS(int node, lld d=0, int label=-1){
	dist[node]=d;
	lab[node]=label;
	trav(a,nei[node]){
		if(dist[a.first]==-1){
			if(label==-1)DFS(a.first,d+a.second,a.first);
			else DFS(a.first,d+a.second,label);
		}
	}
}
void st(int node){
	rep(i,0,n)dist[i]=-1;
	DFS(node);
}
int sz[1000000];
bool bl[1000000];
void getsz(int node){
	vis[node]=true;
	sz[node]=1;
	trav(a,nei[node]){
		if(!vis[a.first] && !bl[a.first]){
			getsz(a.first);
			sz[node]+=sz[a.first];
		}
	}
}
int getcent(int node, int treesz){
	trav(a,nei[node]){
		if(!bl[a.first] && sz[node]>sz[a.first] && sz[a.first]*2>treesz){
			return getcent(a.first,treesz);
		}
	}
	return node;
}
void res(int node){
	vis[node]=false;
	trav(a,nei[node]){
		if(!vis[a.first] && !bl[a.first]){
			res(a.first);
		}
	}
}
int cnt[1000000];
vector<pair<lld,int> >V;
int tt[1000000];
int exc;
lld test(int node){
	exc=-1;
	st(node);
	V.clear();
	rep(i,0,n)cnt[i]=0,tt[i]=0;
	rep(i,0,n){
		V.push_back({-dist[i],lab[i]});
		if(lab[i]>0)tt[lab[i]]++;
	}
	sort(V.begin(),V.end());
	int tot=0;
	lld ans=0;
	trav(a,V){
		if(tot==k)continue;
		lld D=-a.first;
		int v=a.second;
		
		if(2*(cnt[v]+1)<=k && n-1-tt[v]>=cnt[v]+1){
			cnt[v]++;
			tot++;
			ans+=2*D;
			//cout<<D<<" "<<v<<" "<<tt[v]<<" "<<cnt[v]<<" "<<k<<endl;
		}else{
			exc=v;
		}
	}//cout<<endl;
	if(tot<k)ans=-1;
	return ans;
}
void solve(){
	cin>>n>>k;
	if(k==n)k--;
	nei.clear();
	nei.resize(n);
	rep(i,0,n)bl[i]=false;
	rep(i,0,n-1){
		int x,y;
		lld c;
		cin>>x>>y>>c;
		x--;y--;
		nei[x].push_back({y,c});
		nei[y].push_back({x,c});
	}
	
	lld ans=0;
	rep(i,0,n)ans=max(ans,test(i));
	//if(ans!=44 && k>4)assert(false);
	cout<<ans<<"\n";
	//~ int ver=0;
	//~ while(true){
		//~ if(bl[ver])break;
		//~ rep(i,0,n)vis[i]=false;
		//~ getsz(ver);
		//~ int S=sz[ver];
		//~ int cen=getcent(ver,S);
		//~ res(cen);
		//~ ans=max(ans,test(cen));
		//~ if(exc==-1){
			//~ cout<<ans<<"\n";
			//~ return;
		//~ }
		//~ bl[cen]=true;
		//~ ver=exc;
	//~ }
	//~ cout<<ans<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	cin>>tt;
	if(tt>1)assert(false);
	while(tt--){
		solve();
	}
}