#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<queue>
#include<vector>
#define int long long
const int Q=200005;
const int INF=(1<<30);
typedef long long ll;
#define rg register int
#define cint const register int
//char ibuf[1<<21],*IP1=ibuf,*IP2=ibuf;
//#define gc() (IP1==IP2&&(IP2=(IP1=ibuf)+fread(ibuf,1,1<<21,stdin),IP1==IP2)?EOF:*IP1++)
#define gc() getchar()
inline bool ig(const char c){return c>=48&&c<=57;}
inline void read(int &oi){char c;int f=1,res=0;while(c=gc(),(!ig(c))&&c^'-');c^'-'?res=(c^48):f=-1;while(c=gc(),ig(c))res=res*10+(c^48);oi=f*res;}
inline void print(int oi){char io[23];int l=0;if(oi<0)putchar('-'),oi=~oi+1;do io[++l]=(oi%10+48);while(oi/=10);for(;l;--l)putchar(io[l]);}
inline void write(cint oi,const char c){print(oi);putchar(c);}
int n,m,sz1,sz2,T;
int h[Q],ce;struct Edge{int to,nxt,vl;}e[Q<<1];
inline void edge(cint x,cint y,cint z){e[++ce]=(Edge){y,h[x],z};h[x]=ce;}
inline void gph(cint x,cint y,cint z){edge(x,y,z);edge(y,x,z);}
struct info{
	int v1,v3;std::priority_queue<int,std::vector<int>,std::greater<int>>f,s,t;info()=default;
	inline void insert(cint x){
		rg v;f.push(x-v1);if(f.size()>(unsigned)sz1)v=f.top(),f.pop(),s.push(v+v1);
		if(s.size()>(unsigned)sz2)v=s.top(),s.pop(),t.push(v-v3);if(t.size()>(unsigned)sz1)t.pop();
	}
	inline int Gval(){rg res;if(f.size())return res=f.top()+v1,f.pop(),res;if(s.size())return res=s.top(),s.pop(),res;if(t.size())return res=t.top()+v3,t.pop(),res;return assert(0),-1;}
	inline int size(){return f.size()+s.size()+t.size();}
	inline void Inc(cint x){v1+=x;v3-=x;}
	inline void clear(){v1=v3=0;for(;!f.empty();f.pop());for(;!s.empty();s.pop());for(;!t.empty();t.pop());}
};
inline void mg(info&x,info&y){if(x.size()<y.size())std::swap(x,y);for(;y.size();x.insert(y.Gval()));}
info f[Q];
inline void dfs(cint x,cint fa){
	f[x].clear();f[x].insert(0);
	for(rg i=h[x];i;i=e[i].nxt){
		cint y=e[i].to;if(y==fa)continue;dfs(y,x);
		f[y].Inc(e[i].vl<<1);mg(f[x],f[y]);
	}
}
signed main(){
	read(T);for(;T--;){
		read(n);read(m);sz1=m>>1,sz2=m&1;for(rg i=1;i<=n;++i)h[i]=0;ce=0;
		for(rg i=1,x,y,z;i<n;++i)read(x),read(y),read(z),gph(x,y,z);
		dfs(1,0);rg res=0;for(;f[1].size();res+=f[1].Gval());write(res,'\n');
	}
	return 0;
}