#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
#define lc (k << 1)
#define rc (k << 1 | 1)
#define lowbit(x) ((x) & -(x))
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))
#define fir first
#define sec second
#define pb push_back
#define il inline
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define i128 __int128
#define f128 __float128
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << (x) << "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> using vc = vector<T>;
template<class Tx, class Ty>
il void chkmx(Tx& x, const Ty y) {x = max<common_type_t<Tx, Ty>>(x, y);}
template<class Tx, class Ty>
il void chkmn(Tx& x, const Ty y) {x = min<common_type_t<Tx, Ty>>(x, y);}
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
bool ms;

const int N = 20005, M = 25;
int head[N], cnt;
int dep[N], sz[N];
int a[N], b[N];
ll f[N][M], tmp[M];
int k;

struct node {
    int to, nxt;
} e[N << 1];

void init(int n) {
    cnt = 0;
    memset(head, -1, sizeof(head[0]) * (n + 1));
}

void add(int u, int v) {
    e[cnt] = {v, head[u]};
    head[u] = cnt++;
}

void adde(int u, int v) {
    add(u, v);
    add(v, u);
}

void dfs1(int u, int f) {
    sz[u] = 1;
    for(int i = head[u];~i;i = e[i].nxt) {
        int v = e[i].to;
        if(v == f)
            continue;
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int fa, ll lim) {
    f[u][0] = 0;
    int s = 1;
    for(int i = head[u];~i;i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa)
            continue;
        dfs2(v, u, lim);
        memset(tmp, 0x3f, sizeof(tmp));
        rep(j, 0, min(s - 1, k)) {
            rep(l, 0, min(sz[v] - 1, k)) {
                if(j + l > k)
                    break;
                if(f[u][j] + f[v][l] + b[v] <= lim)
                    chkmn(tmp[j + l], max(f[u][j], f[v][l] + b[v]));
                if(j + l + 1 <= k && f[u][j] + f[v][l] + a[v] <= lim)
                    chkmn(tmp[j + l + 1], max(f[u][j], f[v][l] + a[v]));
            }
        }
        s += sz[v];
        rep(j, 0, min(s - 1, k))
            f[u][j] = min(tmp[j], llinf);
    }
}

struct Edge {
    int u, v, a, b;
} edge[N];

void solve() {
    int n;
    cin >> n >> k;
    init(n);
    rep(i, 1, n - 1) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        adde(u, v);
        edge[i] = {u, v, a, b};
    }
    dep[1] = 1;
    dfs1(1, 1);
    rep(i, 1, n - 1) {
        int u = edge[i].u, v = edge[i].v, a = edge[i].a, b = edge[i].b;
        if(u < v)
            swap(u, v);
        ::a[u] = a, ::b[u] = b;
    }
    auto check = [&](ll mid) -> bool {
        dfs2(1, 1, mid);
        return f[1][k] <= mid;
    };
    ll l = 1, r = 1e18, ans = r;
    while(l <= r) {
        ll mid = l + r >> 1;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans << "\n";
}

bool mt;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cerr << fabs(&ms - &mt) / 1024 / 1024 << "\n";
    int t;
    cin >> t;
    while(t--)
        solve();
    cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}