#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

void upd(int &a,const int &b){ if(a==-1||a>b)a=b; }
const int maxn = 21000;
const int maxk = 22;
const int inf  = 1e15;

int n,K;
vector< tuple<int,int,int> >E[maxn];
int ff[maxn],fa[maxn],fb[maxn],siz[maxn];

void dfs(const int x)
{
	siz[x]=1;
	for(auto [y,a,b]:E[x]) if(y!=ff[x])
	{
		ff[y]=x;
		fa[y]=a,fb[y]=b;
		dfs(y);
		siz[x]+=siz[y];
	}
}

int f[maxn][maxk],nf[maxk];
int dp(const int x,const int mid)
{
	vector<int>son;
	for(auto [y,a,b]:E[x]) if(y!=ff[x])
	{
		if(!dp(y,mid)) return 0;
		son.push_back(y);
	}
	
	memset(f[x],-1,sizeof f[x]);
	f[x][0]=0;
	int sx=1;
	for(auto y:son)
	{
		memset(nf,-1,sizeof nf);
		for(int kx=0;kx<=K&&kx<sx;kx++) if(f[x][kx]!=-1)
		{
			for(int ky=0;kx+ky<=K&&ky<=siz[y];ky++) if(f[y][ky]!=-1)
			{
				if(f[x][kx]+f[y][ky]<=mid)
					upd(nf[kx+ky],max(f[x][kx],f[y][ky]));
			}
		}
		memcpy(f[x],nf,sizeof f[x]);
		sx+=siz[y];
	}
	if(x==1&&f[x][K]==-1) return 0;
	
	for(int k=K;k>=0;k--)
	{
		int ka= (k>0&&f[x][k-1]!=-1)?f[x][k-1]+fa[x]:inf;
		int kb= (f[x][k]!=-1)?f[x][k]+fb[x]:inf;
		
		f[x][k]=min(ka,kb);
		if(f[x][k]>mid) f[x][k]=-1;
	}
	
	return 1;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>K;
		for(int i=1;i<=n;i++)
		{
			vector< tuple<int,int,int> >_;
			E[i].swap(_);
		}
		
		int sum=0;
		for(int i=1;i<n;i++)
		{
			int x,y,a,b; cin>>x>>y>>a>>b;
			E[x].emplace_back(y,a,b);
			E[y].emplace_back(x,a,b);
			sum+=max(a,b);
		}
		ff[1]=0; fa[1]=fb[1]=0;
		dfs(1);
		
		int l=1,r=sum;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if( dp(1,mid) ) r=mid-1;
			else l=mid+1;
		}
		cout<<r+1<<'\n';
	}
	
	return 0;
}