#include <bits/stdc++.h>
typedef long long ll;
const ll inf=1e18;
using namespace std;
int T,n,k,head[20010],o=0,sz[20010];
ll x,f[20010][21],g[21];
struct edge{
	int to,link,a,b;
}e[40010];
void add_edge(int u,int v,int a,int b){
	e[++o]={v,head[u],a,b},head[u]=o;
	e[++o]={u,head[v],a,b},head[v]=o;
}
void dfs(int u,int pre){
	for(int i=1;i<=k;i++) f[u][i]=inf;
	f[u][0]=0,sz[u]=1;
	for(int i=head[u],v;i;i=e[i].link) if((v=e[i].to)^pre){
		dfs(v,u);
		for(int j=k;j>=0;j--) f[v][j]=min(f[v][j]+e[i].b,(j>0?f[v][j-1]:inf)+e[i].a);
		for(int j=0;j<=k;j++) g[j]=inf;
		for(int j=0;j<=min(sz[v],k);j++) for(int l=0;l<sz[u]&&j+l<=k;l++) if(f[v][j]+f[u][l]<=x){
			g[j+l]=min(g[j+l],max(f[v][j],f[u][l]));
		}
		for(int j=0;j<=k;j++) f[u][j]=g[j];
		sz[u]+=sz[v];
	}
}
void sol(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) head[i]=0;o=0;
	for(int i=1,u,v,a,b;i<n;i++) scanf("%d%d%d%d",&u,&v,&a,&b),add_edge(u,v,a,b);
	ll l=0,r=2e13,ans=r;
	while(l<=r){
		x=(l+r)>>1;
		dfs(1,0);
		if(f[1][k]<=x) ans=x,r=x-1;
		else l=x+1;
	}
	printf("%lld\n",ans);
}
int main(){
	scanf("%d",&T);
	while(T--) sol();
}