#include <bits/stdc++.h>

using namespace std;

const int maxn = 20025;
const int maxk = 21;
const int64_t INF = 1e18;

vector<tuple<int,int,int>> g[maxn];
vector<int> ord;
int pa[maxn];
void dfs(int i, int f) {
    pa[i] = f;
    ord.push_back(i);
    for (auto [j, a, b]: g[i]) if (j != f) {
        dfs(j, i);
    }
}

array<int64_t,maxk> dp[maxn];
int sz[maxn];

bool ok(int64_t diam, int k) {
    for (int i: ord) {
        sz[i] = 1;
        dp[i][0] = 0;
        for (auto [j, a, b]: g[i]) if (j != pa[i])  {
            array<int64_t,maxk> tmp;
            for (int x = 0; x < sz[j]; x++)
                tmp[x] = dp[j][x] + b;
            for (int x = 0; x < sz[j] && x + 1 < maxk; x++)
                tmp[x + 1] = min(tmp[x + 1], dp[j][x] + a);
            sz[j] = min(maxk, sz[j] + 1);
            for (int x = 0; x < sz[j]; x++)
                dp[j][x] = tmp[x];

            for (int x = 0; x < sz[i] + sz[j] && x < maxk; x++)
                tmp[x] = INF;
            for (int x = 0; x < sz[i]; x++)
                for (int y = 0; y < sz[j] && x + y < maxk; y++)
                    if (dp[i][x] + dp[j][y] <= diam)
                        tmp[x + y] = min(tmp[x + y], max(dp[i][x], dp[j][y]));

            sz[i] = min(maxk, sz[i] + sz[j]);
            for (int x = 0; x < sz[i]; x++)
                dp[i][x] = tmp[x];
        }
    }
    return dp[1][k] < INF;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            g[i].clear();
        ord.clear();

        for (int i = 1; i < n; i++) {
            int u, v, a, b;
            cin >> u >> v >> a >> b;
            g[u].emplace_back(v, a, b);
            g[v].emplace_back(u, a, b);
        }
        dfs(1, 0);
        reverse(ord.begin(), ord.end());
        // string v;
        // for (int x = 0; x < 10; x++) {
        //    v += char('0' + ok(x, k));
        // }
        // cerr << v;
        // cerr << endl;
        // continue;

        int64_t x = -1;
        for (int64_t s = 1LL << 50; s; s >>= 1) { // TODO
            if (not ok(x + s, k)) {
                x += s;
            }
        }
        x += 1;

        cout << x << '\n';
    }
    return 0;
}