#include <cstdio>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <cstring>
#include <array>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
#include <ctime>
#include <cstdlib>
#include <random>
#include <set>
#include <ctime>
#include <map>
#include <stack>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
#define reg register
#define fo(a,b,c) for(reg ll a=b;a<=c;++a)
#define re(a,b,c) for(reg ll a=b;a>=c;--a)
#define pii pair<ll,ll>
#define fi first
#define pb push_back
#define se second
#define ite set<ll> ::iterator
using namespace std;
//const ll mod=998244353;
inline ll gi()
{
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x * f;
}
ll _=1;
const ll inf=1e17;
const ll N=10005;
ll dp[N],ans[N],nxt[N],fa[N],val[N],f[N];
vector<pii> vec[N];
ll fd(ll x)
{
	if(fa[x]==x) return x;
	return fa[x]=fd(fa[x]);
}
void add(ll st,ll ed,ll w)
{
	val[st]+=w;
	while(nxt[st]!=ed)
	{
		if(val[st]+dp[st]>dp[nxt[st]])
		{
			val[st]+=val[nxt[st]];
			fa[nxt[st]]=st;
			nxt[st]=nxt[nxt[st]];
		}
		else break;
	}
}
void sol()
{
	ll n=gi(),m=gi();
	fo(i,1,m)
	{
		ll l=gi()+1,r=gi(),w=gi();
		vec[r].pb({l,w});
	}
	fo(i,0,n) ans[i]=0,f[i]=-inf;
	fo(j,0,n)
	{
		fo(i,0,n)
		{
			dp[i]=-inf;
			fa[i]=i;
			val[i]=0;
			nxt[i]=i+1;
		}
		dp[j]=0;
		fo(i,j+1,n)
		{
			for(pii p:vec[i])
			{
				if(p.fi<=j) continue;
				add(p.fi-1,i,p.se);
			}
			dp[i]=max(f[i-1],dp[fd(i-1)]+val[fd(i-1)]);
		}
		fo(i,j+1,n)
		{
			ans[i-j]=max(ans[i-j],dp[i]);
		}
		fo(i,0,n) f[i]=dp[i];
	}
	fo(i,1,n)
	{
		ans[i]=max(ans[i-1],ans[i]);
		cout<<ans[i]<<" ";
		vec[i].clear();
	}
}
int main()
{
	_=gi();
	while(_--)
	{
		sol();
		printf("\n");
	}
	return 0;
}