#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); i++)
#define revrep(i, a, n) for (auto i = n; i >= (a); i--)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } else return 0; }
using namespace std;

template<class A, class B> string to_string(pair<A, B> p);
template<class A> string to_string(A v) {
	bool first = 1;
	string res = "{";
	for (auto x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(H h, T... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;



int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int cas; cin >> cas; while (cas--) {
		int n, k; cin >> n >> k;
		vector<vector<tuple<int, int, int>>> g(n);
		rep(i, 1, n - 1) {
			int u, v, a, b; cin >> u >> v >> a >> b;
			u--, v--;
			g[u].emplace_back(v, a, b);
			g[v].emplace_back(u, a, b);
		}

		auto check = [&](ll guess) {
			static vector<vector<ll>> dp;
			dp.resize(n);
			
			auto dfs = [&](auto &dfs, int now, int fa) -> void {
				auto &cur = dp[now];
				cur.assign(1, 0ll);
				for (auto [v, a, b]: g[now]) if (v != fa) {
					dfs(dfs, v, now);
					auto &sondp = dp[v];
					vector<ll> ndp(min(sz(dp) + sz(sondp), k + 1), 1ll << 60);
					rep(i, 0, sz(dp) - 1) {
						rep(j, 0, sz(sondp) - 1) {
							if (i + j > k) break;
							if (cur[i] + sondp[j] + b <= guess) chmin(ndp[i + j], max(cur[i], sondp[j] + b));
							if (i + j + 1 <= k && cur[i] + sondp[j] + a <= guess) chmin(ndp[i + j + 1], max(cur[i], sondp[j] + a));
						}
					}
					swap(cur, ndp);
				}
			};
			dfs(dfs, 0, -1);
			return dp[0][k] != 1ll << 60;
		};
		
		ll lo = 0, hi = 1ll * (n - 1) * (ll)(1e9 + 1);
		while (lo < hi) {
			ll mid = (lo + hi) >> 1;
			if (check(mid)) hi = mid;
			else lo = mid + 1;
		}
		printf("%lld\n", hi);
	}
	return 0;
}