#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
//#define int long long
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
//	system("fc .out .ans");
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
bool M1;
const int N=1e4+5;
ll f[2][N],g[2][N],w[N],h[N],d[N],ans[N];
vector<PII> vec[N];
struct dsu {
	int fa[N];
	void init(int n) {
		rep(i,0,n)
		fa[i]=i;
	}
	int find(int x) {
		if(fa[x]!=x)
			fa[x]=find(fa[x]);
		return fa[x];
	}
	void to(int u,int v) {
		fa[u]=v;
	}
}; dsu pre,suf;
void merge(int x,int n) {
	if(h[x]>=0) {
		int p=pre.find(x-1);
		pre.to(x,x-1);
		suf.to(x-1,x);
		d[p]+=d[x];
		int r=suf.find(x);
		if(r!=n) {
			++r;
			h[r]+=h[x];
			merge(r,n);
		}
	}
}
void solve() {
	int n,m;
	scanf("%d%d",&n,&m);
	rep(i,0,n)
	vec[i].clear();
	while(m--) {
		int l,r,val;
		scanf("%d%d%d",&l,&r,&val);
		vec[r].push_back(make_pair(l,val));
	}
	rep(i,0,n)
	f[0][i]=g[0][i]=-INFLL;
	f[0][0]=g[0][0]=0;
	rep(k,0,n) {
		rep(i,0,n) {
			w[i]=h[i]=-INFLL;
			d[i]=0;
			if(k)
				f[k&1][i]=g[k&1][i]=-INFLL;
		}
		pre.init(n);
		suf.init(n);
		rep(i,k,n) {
			if(k)
				g[k&1][i]=max(g[(k-1)&1][i-1],f[(k-1)&1][i-1]);
			w[i]=g[k&1][i];
			if(i!=k) {
				int x=pre.find(i-1);
				h[i]=(w[x]+d[x])-w[i];
				merge(i,i);
			}
			for(auto x:vec[i]) {
				int p=x.first,val=x.second;
				int l=pre.find(p),r=suf.find(p);
				d[l]+=val;
				if(r!=i) {
					++r;
					h[r]+=val;
					merge(r,i);
				}
			}
			if(i!=k) {
				int x=pre.find(i-1);
				f[k&1][i]=w[x]+d[x];
			}
		}
		ans[n-k]=max(f[k&1][n],g[k&1][n]);
	}
	rep(i,1,n)
	printf("%lld ",ans[i]);
	puts("");
}
bool M2;
signed main() {
	//file_IO();
	int testcase=1;
	scanf("%d",&testcase);
	while(testcase--)
		solve();
	fprintf(stderr,"used time = %ldms\n",1000*clock()/CLOCKS_PER_SEC);
	fprintf(stderr,"used memory = %lldMB\n",(&M2-&M1)/1024/1024);
	return 0;
}