#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define il inline
#define pb push_back
#define px first
#define py second

const int inf = 1e9;
const int N = 10005;
int n, m, f[2][N], fa[N], dt[N], val[N], ans[N];
vector<pii> bar[N];

int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
void work(){
	scanf("%d %d", &n, &m); f[0][0] = f[1][0] = 0;
	for(int i = 1; i <= n; i ++) bar[i].clear(), f[0][i] = f[1][i] = 0;
	for(int i = 1; i <= m; i ++){
		int l, r, v; scanf("%d %d %d", &l, &r, &v);
		l ++; bar[r].pb({l, v});
	}
	for(int i = 1; i <= n; i ++){
		f[0][i] = f[0][i - 1];
		for(auto x: bar[i]) f[0][i] += x.py;
	}
	ans[n] = f[0][n]; int now = 1, lst = 0;
	for(int d = 1; d < n; d ++){
		for(int i = 1; i <= n; i ++){f[now][i] = f[lst][i - 1]; fa[i] = i; dt[i] = val[i] = 0;}
		f[now][d - 1] = - inf;
		for(int i = d; i <= n; i ++){
			val[i] = f[now][i - 1];
			int lp = find(i - 1);
			if(i > d && val[lp] + dt[lp] >= val[i]){val[i] = val[lp]; dt[i] = dt[lp]; fa[lp] = i;}
			for(auto x: bar[i]){
				int l = x.px, v = x.py;
				if(l < d) continue;
				int lp = find(l); dt[lp] += v;
				while(lp < i){
					int nxt = find(lp + 1);
					if(val[lp] + dt[lp] >= val[nxt]){val[nxt] = val[lp]; dt[nxt] += dt[lp]; fa[lp] = nxt; lp = nxt;}
					else break;
				}
			}
			f[now][i] = max(f[now][i], val[i] + dt[i]);
		}
		ans[n - d] = f[now][n]; 
		swap(now, lst);
	}
	for(int i = 1; i <= n; i ++) printf("%d ", ans[i]);
	puts(""); return;
}
int main(){
	int t; scanf("%d", &t);
	while(t --) work(); return 0;
}