#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
//#define N
using namespace std;
const int N=10005;
int n,m,g[N],fa[N],h[N],dp[N],R[N];
int ans[N];
vector<pa>G[N];
inline int gf(int k)
{
	while (k!=fa[k]) k=fa[k]=fa[fa[k]];
	return k;
}
void BellaKira()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int l,r,v;
		cin>>l>>r>>v;
		G[r].push_back(mp(l,v));
	}
	for (int i=0;i<=n;i++) g[i]=0;
	for (int i=0;i<=n;i++)
	{
		for (auto [l,v]:G[i]) g[i]+=v;
		g[i+1]=g[i];
	}
	ans[n]=g[n];
	for (int t=1;t<n;t++)
	{
		g[n]=inf;
		for (int i=t;i<=n;i++) fa[i]=i,R[i]=i;
		for (int i=t;i<=n;i++) h[i]=g[i]-g[i-1];
		for (int i=t+1;i<=n;i++)
		{
			for (auto [l,v]:G[i])
			{
				if (l<t) continue;
				l=gf(l);
				while (1)
				{
					if (v<=h[l])
					{
						h[l]-=v;
						break;
					}
					v-=h[l];
					int r=R[l]+1;
					fa[r]=l;
					R[l]=R[r];
					h[l]=h[r];
				}
			}
			int p=gf(i);
			assert(R[p]>=i);
			dp[i]=g[R[p]]-h[p];
		}
		ans[n-t]=dp[n];
		for (int i=0;i<=n;i++) g[i]=dp[i];
	}
	for (int i=1;i<=n;i++) cout<<ans[i]<<' ';
	cout<<'\n';
	for (int i=1;i<=n;i++) vector<pa>().swap(G[i]);
		
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	cin>>T;
	while (T--)
	{
		BellaKira();
	}
}