//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int n,m;
int u[33],v[33],a[33],b[33];
vector<vector<int>> vs;
vector<int> cur;
void init(int x)
{
	if(x==n)
	{
		vs.pb(cur);
		return ;
	}
	for(int i=0;i<=x;i++) if(i==x||cur[i]==i)
	{
		cur.pb(i);
		init(x+1);
		cur.pop_back();
	}
}
int dp[62][23000][32];
int tr[23000][10][10];
map<vector<int>,int> Mp;
inline void upd(int &a,int b){a=max(a,b);}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=m;i++)
		{
			cin>>u[i]>>v[i]>>a[i]>>b[i];
			u[i]--;
			v[i]--;
		}
		vs.clear();
		cur.clear();
		init(0);
		int M=sz(vs);
		Mp.clear();
		for(int i=0;i<M;i++)
			Mp[vs[i]]=i;
		for(int i=0;i<M;i++)
			for(int a=0;a<n;a++) if(vs[i][a]==a)
				for(int b=a+1;b<n;b++) if(vs[i][b]==b)
				{
					vector<int> nv=vs[i];
					for(auto &x:nv) if(x==b) x=a;
					tr[i][a][b]=Mp[nv];
				}
		memset(dp,-1,sizeof(dp));
		dp[0][M-1][0]=0;
		vector<array<int,4>> vec;
		for(int i=1;i<=m;i++)
		{
			if(u[i]>v[i]) swap(u[i],v[i]);
			if(a[i]<=b[i])
			{
				vec.push_back({a[i],0,u[i],v[i]});
				vec.push_back({b[i],2,u[i],v[i]});
			}
			else
			{
				vec.push_back({a[i],2,u[i],v[i]});
				vec.push_back({b[i],1,u[i],v[i]});
			}
		}
		srt(vec);
		for(int i=0;i<m+m;i++)
			for(int j=0;j<M;j++) for(int a=0;a<=m;a++) if(~dp[i][j][a])
			{
				int u=vs[j][vec[i][2]];
				int v=vs[j][vec[i][3]];
				if(u>v) swap(u,v);
				if(vec[i][1]==2)
				{
					if(u==v)
						upd(dp[i+1][j][a],dp[i][j][a]);
					else
						upd(dp[i+1][tr[j][u][v]][a],dp[i][j][a]+vec[i][0]);
				}
				if(vec[i][1]==0)
				{
					if(u==v)
					{
						upd(dp[i+1][j][a],dp[i][j][a]);
						upd(dp[i+1][j][a+1],dp[i][j][a]);
					}
					else
					{
						upd(dp[i+1][j][a],dp[i][j][a]);
						upd(dp[i+1][tr[j][u][v]][a+1],dp[i][j][a]+vec[i][0]);
					}
				}
				if(vec[i][1]==1)
				{
					if(u==v)
					{
						upd(dp[i+1][j][a],dp[i][j][a]);
						upd(dp[i+1][j][a+1],dp[i][j][a]);
					}
					else
					{
						upd(dp[i+1][j][a+1],dp[i][j][a]);
						upd(dp[i+1][tr[j][u][v]][a],dp[i][j][a]+vec[i][0]);
					}
				}
			}
		for(int i=0;i<=m;i++)
		{
			int res=dp[m+m][0][i];
			cout<<res<<'\n';
		}
	}
	return 0;
}