#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 10005;
const LL INF = -0x3f3f3f3f3f3f3f3f;

int n, m;
vector<pair<int, int> > v[N];
LL f[N], g[N], ans[N];
int fa[N];
LL d[N], s[N];

inline int Gfa(int i)
{
	return i == fa[i] ? i : fa[i] = Gfa(fa[i]);
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T -- )
	{
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; i ++ ) v[i].clear();
		for(int i = 1; i <= m; i ++ )
		{
			int l, r, x;
			scanf("%d%d%d", &l, &r, &x);
			v[r].emplace_back(l, x);
		}
		
		f[0] = 0;
		for(int i = 1; i <= n; i ++ )
		{
			f[i] = f[i - 1];
			for(auto &j : v[i]) f[i] += j.second;
		}
		ans[n] = f[n];
		for(int i = n - 1; i >= 1; i -- )
		{
			d[0] = s[0] = 0, g[0] = INF;
			for(int j = 1; j <= n; j ++ )
			{
				g[j] = f[j - 1];
				fa[j] = g[j - 1] >= g[j] ? j - 1 : j;
				d[j] = s[j] = 0;
			}
			f[0] = INF;
			for(int j = 1; j <= n; j ++ )
			{
				for(auto &k : v[j])
				{
					d[k.first] += k.second;
					s[Gfa(k.first)] += k.second;
					if(d[k.first] + g[k.first] >= g[k.first + 1])
					{
						int p = Gfa(k.first), q = Gfa(k.first + 1);
						if(p != q)
						{
							s[p] += s[q];
							fa[q] = p;
						}
					}
				}
				// printf("!%d %d %lld %lld\n", j, Gfa(j), g[Gfa(j)], s[Gfa(j)]);
				f[j] = g[Gfa(j)] + s[Gfa(j)];
			}
			// for(int j = 1; j <= n; j ++ ) printf("%lld ", f[j]);
			// puts("");
			ans[i] = f[n];
		}

		for(int i = 1; i <= n; i ++ ) printf("%lld ", ans[i]);
		puts("");
	}
	return 0;
}