#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
#define isz(v) (int)(v.size())
using namespace std;

const int maxs=22005;
const int maxn=11;
const int maxm=105;
const int inf=0x3f3f3f3f;

namespace Solve {
	int n,m;
	int cnt;
	array<int,maxn> b;
	array<int,maxn> all[maxs];
	map<array<int,maxn>,int> id;
	int to[maxs][maxn][maxn];
	int f[maxs][maxm];
	int g[maxs][maxm];
	void clear() {
		cnt=0;
		id.clear();
		memset(to,0,sizeof(to));
	}
	void pre(int x,int c) {
		if(x==n+1) {
			all[++cnt]=b;
			id[b]=cnt;
			return ;
		}
		for(int i=1;i<=c;i++) {
			b[x]=i;
			pre(x+1,c+(i==c));
		}
	}
	array<int,maxn> deal(array<int,maxn> v) {
		int cnt=0;
		array<int,maxn> vis={};
		for(int i=1;i<=n;i++) {
			if(!vis[v[i]]) {
				vis[v[i]]=++cnt;
			}
			v[i]=vis[v[i]];
		}
		return v;
	}
	void ckmax(int &x,int y) {
		x=max(x,y);
	}
	void main(int tid) {
		cin>>n>>m;
		pre(1,1);
		for(int s=1;s<=cnt;s++) {
			for(int i=1;i<=n;i++) {
				for(int j=1;j<=n;j++) {
					if(all[s][i]==all[s][j]) {
						continue;
					}
					auto c=all[s];
					for(int k=1;k<=n;k++) {
						if(c[k]==all[s][j]) {
							c[k]=all[s][i];
						}
					}
					to[s][i][j]=id[deal(c)];
				}
			}
		}
		int ex=0;
		vector<array<int,4>> es;map<pii,bool> vis;
		for(int i=1;i<=m;i++) {
			int x,y,a,b;
			cin>>x>>y>>a>>b;assert((!vis[{x,y}]));vis[{x,y}]=vis[{y,x}]=true;
			if(a<=b) {
				es.push_back({a,0,x,y});
				es.push_back({b,2,x,y});
			} else {
				ex++;
				es.push_back({b,1,x,y});
				es.push_back({a,2,x,y});
			}
		}
		sort(es.begin(),es.end());
		memset(f,-0x3f,sizeof(f));
		f[cnt][ex]=0;
		for(auto p:es) {
			int x=p[2],y=p[3];
			memset(g,-0x3f,sizeof(g));
			for(int s=1;s<=cnt;s++) {
				int t=s,val=0;
				if(to[s][x][y]) {
					t=to[s][x][y];
					val=p[0];
				}
				if(p[1]==2) {
					for(int i=0;i<=m;i++) {
						ckmax(g[t][i],f[s][i]+val);
					}
				} else {
					for(int i=0;i<=m;i++) {
						ckmax(g[s][i],f[s][i]);
					}
					if(p[1]==0) {
						for(int i=0;i<=m-1;i++) {
							ckmax(g[t][i+1],f[s][i]+val);
						}
					} else {
						for(int i=0;i<=m-1;i++) {
							ckmax(g[t][i-1],f[s][i]+val);
						}
					}
				}
			} 
			memcpy(f,g,sizeof(f));
		}
		for(int i=0;i<=m;i++) {
			cout<<f[1][i]<<"\n";
		}
	}
	void init() {
		
	}
}

signed main() {
//	freopen("mst.in","r",stdin);
//	freopen("mst.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	Solve::init();
	for(int t=1;t<=T;t++) {
		Solve::main(t);
		Solve::clear();
	}
#ifndef ONLINE_JUDGE
	cerr<<"Time: "<<clock()<<"ms\n";
#endif
}