#include<bits/stdc++.h>
#define N 10005
//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
#define gc() getchar()
#define fi first
#define se second
#define Kamisato return
#define Ayaka 0;
//#define CHECK_MEMORY ___JQH___
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define int long long
const int inf=1e9;
const ll INF=2e18;
bool Memory_Begin;
namespace IO{const int SIZE=(1<<21)+1;char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr;inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf,fflush(stdout);}inline void putc(char x){*oS++=x;if(oS==oT)flush();}template <class I>inline void read(I &x){for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;}template <class I>inline void print(I x){if(!x)putc('0');if(x<0)putc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)putc(qu[qr --]);}inline void reads(string &s){s.clear();for(c=gc();c<33||c>126;)c=gc();for(;c>=33&&c<=126;c=gc())s.push_back(c);}inline void prints(string s){for(char c:s)putc(c);}struct Flusher_ {~Flusher_(){flush();}}io_flusher_;}
using IO::read;using IO::putc;using IO::print;using IO::reads;using IO::prints;
template<class I>I updiv(I x,I y){return (x%y==0?x/y:x/y+1);}
template<class I>bool cmin(I &x,I y){if(x>y)return x=y,1;return 0;}
template<class I>bool cmax(I &x,I y){if(x<y)return x=y,1;return 0;}

int n,m,prt[N];
ll f[2][N],ans[N],dt[N],val[N];
vector<pii>c[N];
int getf(int x){return prt[x]==x?x:prt[x]=getf(prt[x]);}
void solve()
{
	read(n),read(m);
	for(int i=1,l,r,v;i<=m;i++)
	{
		read(l),read(r),read(v),l++;
		c[r].push_back({l,v});
	}
	for(int i=1;i<=n;i++)//d=0
	{
		f[0][i]=f[0][i-1];
		for(pii P:c[i]) f[0][i]+=P.se;
	}
	ans[n]=f[0][n];
	for(int d=1;d<n;d++)//d=i-j
	{
		for(int i=1;i<=n;i++) f[d&1][i]=f[(d-1)&1][i-1],prt[i]=i,dt[i]=val[i]=0;
		f[d&1][d-1]=-INF;
		for(int i=d;i<=n;i++)
		{
			val[i]=f[d&1][i-1];
			int las=getf(i-1);
			if(i!=d&&val[las]+dt[las]>=val[i]) val[i]=val[las],dt[i]=dt[las],prt[las]=i;
			for(pii P:c[i])
			{
				int l=P.fi,v=P.se;
				if(l<d) continue;
				l=getf(l),dt[l]+=v;
				while(l<i)
				{
					int t=getf(l+1);
					if(val[l]+dt[l]>=val[t]) val[t]=val[l],dt[t]=dt[l],prt[l]=t,l=t;
					else break;
				}
			}
			cmax(f[d&1][i],val[i]+dt[i]);
		}
		ans[n-d]=f[d&1][n];
	}
}
void clear()
{
	for(int i=1;i<=n;i++) print(ans[i]),putc(" \n"[i==n]); 
	for(int i=0;i<=n;i++) f[0][i]=f[1][i]=0,c[i].clear();
}
bool Memory_End;
signed main()
{
#ifdef CHECK_MEMORY
	cerr<<"Memory: "<<(&Memory_End-&Memory_Begin)/1048576.0<<" MiB\n";
#endif
	int T; read(T);
	while(T--) solve(),clear();
	Kamisato Ayaka
}