#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int l[10005],r[10005];
ll w[10005];
ll dp[2][10005];
vector<int>il[10005],ir[10005];

ll dx[10005];
int bl[10005],br[10005];
int dsu[10005];
ll ans[10005];
int find(int x){
	if(dsu[x]!=x) dsu[x]=find(dsu[x]);
	return dsu[x];
}
void join(int x,int y){
	x=find(x);y=find(y);
	//cout << "join " << x << ' ' << y << endl;
	dsu[y]=x;
	br[x]=br[y];
	dx[x]+=dx[y];
}
void solve(){
	cin >> n >> m;
	for(int i=0; i<=n ;i++){
		il[i].clear();
		ir[i].clear();
	}
	for(int i=1; i<=m ;i++){
		cin >> l[i] >> r[i] >> w[i]; 
		il[l[i]].push_back(i);
		ir[r[i]].push_back(i);
	}
	ll frog=0;
	//cout << "0 ";
	for(int i=1; i<=n ;i++){
		for(auto c:ir[i]) frog+=w[c];
		dp[0][i]=frog;
		//cout << frog << ' ';
	}
	//cout << endl;
	ans[n]=dp[0][n];
	for(int k=1; k<n ;k++){
		int c=k&1;
		int p=c^1;
		for(int j=k; j<=n ;j++){
			dx[j]=dp[p][j]-dp[p][j-1];
			dsu[j]=j;
			bl[j]=j-1;br[j]=j;
		}
		dp[c][k]=0;
		for(int j=k+1; j<=n ;j++){
			for(auto c:ir[j]){
				if(l[c]<k) continue;
				//cout << "haha " << l[c] << ' ' << w[c] << endl;
				
				int frog=find(l[c]);
				dx[frog]-=w[c];
				
				while(frog!=find(j-1) && dx[frog]<=0){
					join(frog,br[frog]+1);
				}
			}
			/*cout << "DSU ";
			for(int i=k; i<=n ;i++){
				if(dsu[i]==i) cout << bl[i] << ' ' << br[i] << ' ' << dx[i] << endl;
			}
			cout << endl;*/
			dp[c][j]=dp[p][j-1]-min(0LL,dx[find(j-1)]);
			if(j-1>k && dx[find(j-1)]<=0) join(j-1,j);
		}/*
		for(int i=k; i<=n ;i++){
			cout << dp[c][i] << ' ';
		}
		cout << endl;*/
		ans[n-k]=dp[c][n];
	}
	for(int i=1; i<=n ;i++){
		cout << ans[i] << ' ';
	}
	cout << '\n';
}
int main(){
	int t;cin >> t;
	while(t--) solve();
}