#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[20100][30];
int n,m;
#define pb push_back
#define vi array<int,3>
vector<vi>g[20100];
ll D,fz[30];
const ll I=1e18;
void dfs(int x,int f){
    dp[x][0]=0;
    for(int i=1;i<=m;i++)dp[x][i]=I;
    for(vi t:g[x])if(t[0]!=f){
        int v=t[0];dfs(v,x);
        for(int i=m;i;i--)dp[v][i]=min(dp[v][i-1]+t[1],dp[v][i]+t[2]);
        dp[v][0]+=t[2];
        for(int i=0;i<=m;i++)fz[i]=I;
        for(int i=0;i<=m;i++)
            for(int j=0;i+j<=m;j++)
            if(dp[x][i]+dp[v][j]<=D)
                fz[i+j]=min(fz[i+j],max(dp[x][i],dp[v][j]));
        for(int i=0;i<=m;i++)dp[x][i]=fz[i];
    }
}
bool chk(){
    dfs(1,0);
    return dp[1][m]<I;
}
void sol(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)g[i].clear();
    for(int i=1,u,v,a,b;i<n;i++){
        scanf("%d%d%d%d",&u,&v,&a,&b);
        g[u].pb({v,a,b});
        g[v].pb({u,a,b});
    }
    ll l=0,r=1e15,at=r+1;
    while(l<=r){
        ll mi=(l+r)>>1;D=mi;
        if(chk())at=mi,r=mi-1;
        else l=mi+1;
    }
    printf("%lld\n",at);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}