#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];
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;
}
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;
}
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;
					res[find(l)]+=v;
				}
				while(1)
				{
					int pos1=find(i),pos2=find(find(i)-1);
					if(pos2<=t) break;
					int res1=f[pos1-1]+res[pos1],res2=f[pos2-1]+res[pos1]+res[pos2];
					if(res1<=res2) mrg(pos2,pos1);
					else break;
				}
				int pos=find(i);
				f[i]=max(pre[i-1],f[pos-1]+res[pos]);
				if(i==t) f[i]=0;
//				printf("%d %d:%d %lld\n",t,i,pos,f[i]);
			}
			for(int i=t;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");
	}
}