#include<bits/stdc++.h>
#define N 10005
using namespace std;
const long long inf=1e18;
int n,m;
int h[N],to[N],nxt[N],w[N],cnt;
void jb(int u,int v,int W){
	to[++cnt]=v;
	w[cnt]=W;
	nxt[cnt]=h[u];
	h[u]=cnt;
}
long long f[N],g[N],ad[N],ans[N];
int fa[N],pr[N];
int getfa(int u){
	if(fa[u]==u) return u;
	return fa[u]=getfa(fa[u]);
}
void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int l,r,v;
		scanf("%d%d%d",&l,&r,&v);
		jb(r,l,v);
	}
	for(int i=1;i<=n;i++) f[i]=-inf;
	f[0]=g[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++) ad[j]=0;
		for(int j=0;j<=n+1;j++) fa[j]=j;
		int ed=0;
		for(int j=1;j<=n;j++){
			if(f[ed]+ad[ed]<f[j]){
				pr[j]=ed;
				fa[ed]=j;
				ed=j;
			}
			for(int o=h[j];o!=0;o=nxt[o]){
				int x=to[o];
				if(x>=ed) ad[ed]+=w[o];
				else{
					x=getfa(x+1);
					int y=pr[x];
					ad[y]+=w[o];
					while(x<=j&&f[y]+ad[y]>=f[x]){
						fa[x]=x+1;
						ad[y]+=ad[x];
						if(x==ed){
							ed=y;
							break;
						}
						x=getfa(x);
						pr[x]=y;
					}
				}
			}
			g[j]=f[ed]+ad[ed];
		}
		ans[n+1-i]=g[n];
		for(int j=1;j<=n;j++) f[j]=g[j-1];
		f[0]=g[0]=-inf;
	}
	for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
	printf("\n");
	for(int i=1;i<=n;i++) h[i]=0;
	cnt=0;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--) solve();
	return 0;
}