#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int T,n,m,k;
long long ans[N];
struct nd
{
	int l,v;
	bool operator <(const nd &b) const
	{
		return l<b.l;
	}
};
vector <nd> hav[N];
long long sum[N];
long long pre[N],f[N];
//in time t:f[i]:cnt=i-t,now=i,max value
int fa[N],R[N];
long long res[N];
int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void mrg(int x,int y)//x<-y
{
	int fx=find(x),fy=find(y);
	if(fx==fy) return;
	res[fx]+=res[fy];
	fa[fy]=fx;R[fx]=R[fy];
}
void clr()
{
	for(int i=1;i<=n;i++) f[i]=0;
	for(int i=1;i<=n;i++) fa[i]=i,res[i]=0,R[i]=i;
}
void init()
{
	for(int i=1;i<=n;i++) hav[i].clear(),sum[i]=0;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<=m;i++)
		{
			int l,r,v;
			scanf("%d%d%d",&l,&r,&v);
			l++;
			hav[r].push_back((nd){l,v});
			sum[r]+=v;
		}
		for(int i=1;i<=n;i++) sort(hav[i].begin(),hav[i].end());
		for(int i=1;i<=n;i++) pre[i]=pre[i-1]+sum[i];
		ans[n]=pre[n];
		for(int t=1;t<=n;t++)
		{
			clr();
			for(int i=t;i<=n;i++)
			{
				for(int j=0;j<hav[i].size();j++)
				{
					int l=hav[i][j].l,v=hav[i][j].v;
					int pos=find(l);
					if(pos<=t) continue;
					int pos2=R[pos]+1;
					res[pos]+=v;
					if(pre[pos-2]+res[pos]>=pre[pos2-2]) mrg(pos,pos2);
				}
				int pos=find(i);
				f[i]=max(pre[i-1],pre[pos-2]+res[pos]);
//				printf("%d %d:%d %lld %lld\n",t,i,pos,res[pos],f[i]);
			}
			for(int i=1;i<=n;i++) pre[i]=f[i];
			ans[n-t]=f[n];
		}
		for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
		printf("\n");
	}
}