#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,n,m;
int _l[10005],_r[10005],_v[10005];
vector <pii> S[10005];

ll dp[10005],ans[10005];

int fa[10005];
int fnd(int u){
	if(fa[u] == u) return u;
	return fa[u] = fnd(fa[u]);
}
ll delta[10005],Mx;
void upd(int cur,int p,int val){//给 <= p 的全都 + val
//	printf("add %d %d %d\n",cur,p,val);
	if(fnd(1) > p) return;
	int u = fnd(p + 1),v;
	if(u > cur){
		Mx += val;
		return;
	}
	delta[u] -= val;
	while(delta[u] <= 0){
		v = fnd(u + 1);
		if(v > cur){
			Mx -= delta[u];
			fa[u] = v;
			return;
		}
		delta[v] += delta[u];
		fa[u] = v;
		u = v;
	}
}

void psh(int cur,ll val){
//	printf("psh %d %lld\n",cur,val);
	if(val <= Mx){
		fa[cur] = cur + 1;
		return;
	}
	delta[cur] = val - Mx;
	Mx = val;
}

void dbg(){
	printf("dbg\n");
	rep(u,1,n) printf("%d ",fnd(u));
	printf("\n");
	rep(u,1,n) printf("%lld ",delta[u]);
	printf("\n");
	printf("Mx=%lld\n",Mx);
}

void solve(){
	scanf("%d%d",&n,&m);
	rep(i,1,n) S[i].clear();
	rep(i,1,m){
		scanf("%d%d%d",&_l[i],&_r[i],&_v[i]);
		_l[i]++;
		S[_r[i]].eb(mkp(_l[i],_v[i]));
//		printf("[%d,%d] %d\n",_l[i],_r[i],_v[i]);
	}
	dp[0] = 0;
	rep(i,1,n){
		dp[i] = dp[i - 1];
		for(pii I:S[i]) dp[i] += I.second;
	}
	rep(p,0,n - 1){
		ans[n - p] = dp[n];
		per(i,n,1) dp[i] = dp[i - 1];
		dp[0] = -linf;
		rep(i,1,p + 1) fa[i] = p + 2;
		rep(i,p + 2,n + 1) fa[i] = i;
		fill(delta,delta + n + 1,0);
		Mx = -inf;
//		rep(i,1,n) printf("%lld ",dp[i]);
//		printf("\n");
		//只有 >= p + 2 的才有意义
//		printf("fix\n");
		rep(i,p + 2,n){
			psh(i,dp[i - 1]);
//			if(i == 4) dbg();
			for(pii I:S[i]) if(I.first >= p + 2) upd(i,I.first,I.second);
			chkmax(dp[i],Mx);
//			if(i == 4) dbg();
		}
//		rep(i,1,n) printf("%lld ",dp[i]);
//		printf("\n");
	}
	rep(i,1,n) printf("%lld ",ans[i]);
	printf("\n");
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}