/*Life is too long to end at a grave*/
#include<bits/stdc++.h>
#define N 100010
#define I_love_Furina return
#define forever 0
#define foreverr 1
#define endl '\n'
#define FIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define db double
#define ull unsigned long long
#define chc cout<<114514<<endl
#define PII pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define int long long
#define mid (r+l>>1)
using namespace std;
int n,T,m,dp[N][31],maxlen[31],son[N],head[N],num;
struct edge{
    int to,nxt,aw,bw;
}a[N<<1];
inline void add(int u,int v,int aw,int bw){
    a[++num].to=v,a[num].aw=aw,a[num].bw=bw,a[num].nxt=head[u],head[u]=num;
}
void dfs(int x,int fa,int lim){
    dp[x][0]=son[x]=0;
    for(int k=head[x];k;k=a[k].nxt){
        int v=a[k].to,aw=a[k].aw,bw=a[k].bw;
        if(v==fa)continue;
        dfs(v,x,lim);
        int so=min(son[x]+son[v]+1,m);
        for(int j=0;j<=so;j++)maxlen[j]=1e18;
        for(int i=0;i<=son[x];i++)
            for(int j=0;j<=son[v]&&i+j<=m;j++){
                if(dp[x][i]+dp[v][j]+aw<=lim)maxlen[i+j+1]=min(maxlen[i+j+1],max(dp[x][i],dp[v][j]+aw));
                if(dp[x][i]+dp[v][j]+bw<=lim)maxlen[i+j]=min(maxlen[i+j],max(dp[x][i],dp[v][j]+bw));
            }
        son[x]=so;
        for(int j=0;j<=so;j++)dp[x][j]=maxlen[j];
    }   
}
inline bool check(int x){
    // memset(maxlen,0x3f,sizeof maxlen);
    //memset(dp,0,sizeof dp);
    //memset(son,0,sizeof son);
    dfs(1,0,x);
    I_love_Furina (dp[1][m]<=x);
}
signed main(){
    IOS;//FIO("");
    cin>>T;
    while(T--){
        cin>>n>>m;
        int l=0,r=0;
        num=0;for(int i=1;i<=n;i++)head[i]=0;
        for(int i=1,u,v,a,b;i<n;i++)cin>>u>>v>>a>>b,r+=max(a,b),add(u,v,a,b),add(v,u,a,b);
        
        while(r-l>2){
            if(check(mid))r=mid;
            else l=mid;
        }
        if(check(l))cout<<l;
        else if(check(mid))cout<<mid;
        else cout<<r;
cout<<endl;
        // dfs(1,0);
        // cout<<maxlen[1][m]<<endl;
    }
    I_love_Furina forever;
}