求助，map 改成 umap 会导致 WA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117#pragma GCC optimize("Ofast")
using namespace std;
using namespace __gnu_pbds;
using uint = unsigned int; using ll = long long; using ull = unsigned long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using ld = long double; using i128 = __int128; using u128 = unsigned __int128;
template<typename T, size_t N, size_t M> using matrix = array<array<T, M>, N>;
template<typename T1, typename T2> bool chkmin(T1& a, const T2& b) { return b < a ? (a = b, true) : false; }
template<typename T1, typename T2> bool chkmax(T1& a, const T2& b) { return b > a ? (a = b, true) : false; }
// template<class... T> void debug(T&&... x) { cout << "(debug) "; ((cout << x << " "), ...); cout << "\n"; }
void fileIO(const string& x) { freopen((x + ".in").c_str(), "r", stdin), freopen((x + ".out").c_str(), "w", stdout); }
mt19937_64 gen(random_device{}());
template<typename T> ostream& operator << (ostream& os, const vector<T>& vec) {
	for(auto it = vec.begin(); it != vec.end(); ++it) (it == vec.begin()) ? (os << *it) : (os << " " << *it);
	return os;
}
template<typename T> istream& operator >> (istream& is, vector<T>& vec) { for(auto& x : vec) is >> x; return is; }
template<typename T, typename U> ostream& operator << (ostream& os, const pair<T, U>& pr) { os << pr.first << ' ' << pr.second; return os; }
template<typename T, typename U> istream& operator >> (istream& is, const pair<T, U>& pr) { is >> pr.first >> pr.second; return is; }

int test_case;
template<typename T> constexpr T inf;
template<> constexpr int inf<int> = 1e9; template<> constexpr uint inf<uint> = 1e9;
template<> constexpr ll inf<ll> = 2e18; template<> constexpr ull inf<ull> = 2e18; template<> constexpr ld inf<ld> = 2e18;

void solution() {
	int n, m; cin >> n >> m;
	struct Edge {
		int u, v;
		ll w;
		int typ, id;
		Edge(int _u, int _v, ll _w, int _typ, int _id)
		: u(_u), v(_v), w(_w), typ(_typ), id(_id) {}
		bool operator < (const Edge &rhs) const {
			return w < rhs.w;
		}
	};
	vector<Edge> edg;
	for(int i = 0; i < m; i++) {
		int u, v; cin >> u >> v; u--, v--;
		ll a, b; cin >> a >> b;
		if(a <= b) {
			edg.emplace_back(u, v, a, +1, i);
			edg.emplace_back(u, v, b, 0, i);
		} else {
			edg.emplace_back(u, v, b, -1, i);
			edg.emplace_back(u, v, a, 0, i);
		}
	}
	sort(edg.begin(), edg.end());

	map<ull, int> mp;

	auto get = [](const ull &info, int u) -> ull { return info >> (u * 4) & 15ULL; };
	auto set = [](ull &info, int u, int p) -> void { info &= ~(15ULL << (u * 4)); info ^= p << (u * 4); };

	constexpr int B = 22000;
	vector<vector<ll> > f(B, vector<ll>(m * 2 + 1, -inf<ll>));
	vector<vector<ll> > nf(B, vector<ll>(m * 2 + 1, -inf<ll>));

	ull bg = 0;
	for(int i = 0; i < n; i++) set(bg, i, i);
	mp[bg] = mp.size();
	f[mp[bg]][m] = 0;

	auto merge = [&](ull info, int u, int v) -> int {
		ull f_u = get(info, u), f_v = get(info, v), new_f = min(f_u, f_v);

		for(int i = 0; i < n; i++) if(get(info, i) == f_u || get(info, i) == f_v) set(info, i, new_f);
		
		if(mp.find(info) == mp.end()) return mp[info] = mp.size();

		return mp[info];
	};

	for(const auto &[u, v, w, typ, eid] : edg) {
		for(int i = 0; i < mp.size(); i++) nf[i].assign(m * 2 + 1, -inf<ll>);

		for(const auto &[info, id] : mp) {
			for(int k = 0; k <= m * 2; k++) if(f[id][k] >= 0) {
				if(typ == +1 || typ == -1) {
					if(get(info, u) != get(info, v)) {
						if(0 <= k + typ && k + typ <= m * 2) chkmax(nf[merge(info, u, v)][k + typ], f[id][k] + w);
						chkmax(nf[id][k], f[id][k]);
					} else {
						if(0 <= k + typ && k + typ <= m * 2) chkmax(nf[id][k + typ], f[id][k]);
						chkmax(nf[id][k], f[id][k]);
					}
				} else {
					if(get(info, u) != get(info, v)) chkmax(nf[merge(info, u, v)][k], f[id][k] + w);
					else chkmax(nf[id][k], f[id][k]);
				}
			}
		}
		f.swap(nf);
	}
	// array<int, 9> ed = {};
	ull ed = 0;
	assert(mp.find(ed) != mp.end());
	// cout << mp.count(ed) << "]\n";
	// if(mp.find(ed) == mp.end()) { cout << "NO!!!"; return; }
	for(int k = 0; k <= m * 2; k++) {
		if(f[mp[ed]][k] >= 0) cout << f[mp[ed]][k] << "\n";
	}
	// cerr << mp.size() << "\n";
}
void sol_clear() {}
void prework() {}

int main() {
	// fileIO("mst");
	ios::sync_with_stdio(false), cin.tie(nullptr);
	prework();
	int test_num = 1; cin >> test_num;
	for(test_case = 1; test_case <= test_num; test_case++) solution(), sol_clear();
	return 0;
}