#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define pi std::pair<int,int>
using std::cin;using std::cout;
constexpr int N=1005,M=10005;
int t,n,m,l[M],r[M],v[M];
long long f[N][N],pre[N][N],d[M];
std::vector<pi >g[N];
signed main(){
//	freopen("road.in","r",stdin);
//	freopen("road.out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	for(cin>>t;t--;){
		cin>>n>>m;for(int i=0;i<n;++i) g[i].clear();
		bool vis=1;
		for(int i=1;i<=m;++i){cin>>l[i]>>r[i]>>v[i];if(l[i]+1!=r[i]) vis=0;}
		if(vis){
			for(int i=1;i<=n;++i) d[l[i]]+=v[i];
			std::sort(d,d+n);
			long long tot=0;
			for(int i=n-1;i>=0;--i){tot+=d[i];cout<<tot<<(i?' ':'\n');}
			continue;
		}
		for(int i=1;i<=n;++i) g[l[i]].emplace_back(r[i],v[i]);
		for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) f[i][j]=0;
		for(int i=1;i<=n;++i){
			long long sum=0;
			for(int k=i-1;k>=0;--k){
				for(pi j:g[k]) if(j.first<=i) sum+=j.second;
				for(int j=i-k;j<=i;++j) f[i][j]=std::max(f[i][j],pre[k][j-i+k]+sum);
			}
			for(int j=1;j<=n;++j) pre[i][j]=std::max(pre[i-1][j],f[i][j]);
		}
		for(int i=1;i<=n;++i) cout<<pre[n][i]<<(i==n?'\n':' ');
	}
	return 0;cout<<"猫屋敷真由";
}//第一百五回 锦衣军查抄宁国府 骢马使弹劾平安州