#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

ll N, K, D;
vector <pair<int, pii>> tree[20005];
ll dp[20005][25];

void init() {
    for(int i = 1; i <= N; i++) tree[i].clear();
}

void DFS(int node, int par) {
    dp[node][0] = 0;
    for(int i = 1; i <= K; i++) dp[node][i] = 1e18;

    for(int i = 0; i < tree[node].size(); i++) {
        ll next = tree[node][i].first, a = tree[node][i].second.first, b = tree[node][i].second.second;
        if(next == par) continue;
        DFS(next, node);

        for(int j = K; j >= 1; j--) dp[next][j] = min(dp[next][j - 1] + a, dp[next][j] + b);
        dp[next][0] += b;

        vector <ll> v(25, 1e18);

        for(int j = 0; j <= K; j++) {
            for(int k = 0; k <= K; k++) {
                if(j + k > K) break;
                if(dp[node][j] + dp[next][k] <= D) v[j + k] = min(v[j + k], max(dp[node][j], dp[next][k]));
            }
        }

        for(int j = 0; j <= K; j++) dp[node][j] = v[j];
    }

    return;
}

void solve() {
    cin >> N >> K;

    init();

    for(int i = 0; i < N - 1; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        tree[a].push_back({b, {c, d}});
        tree[b].push_back({a, {c, d}});
    }

    ll l = 0, r = 1e15, ok = -1;
    while(l <= r) {
        ll m = (l + r) / 2;
        D = m;
        DFS(1, 1);
        if(dp[1][K] < 1e18) {
            ok = m;
            r = m - 1;
        }
        else l = m + 1;
    }

    cout << ok << '\n';

    return;
}

int main(void) {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}