#include <bits/stdc++.h>
using ll = long long;

struct hope {
  int bk;
  ll bkv;
  std::vector<int> fa, nx;
  std::vector<ll> d;
  int find(int u) {
    while (fa[u] != u) u = fa[u] = fa[fa[u]];
    return u;
  }
  hope(ll x) { bk = 0, bkv = x, fa = {0}, nx = {0}, d = {0}; }
  void push_back(ll v) {
    int idx = fa.size();
    fa.push_back(idx);
    if (bkv >= v) {
      fa[idx] = idx - 1;
      nx.push_back(0), d.push_back(0);
      return;
    }
    nx[bk] = idx, d[bk] = v - bkv, bk = idx, bkv = v;
    nx.push_back(idx), d.push_back(0);
  }
  void add(int p, ll v) {
    assert(p < (int)fa.size());
    p = find(p);
    if (p == bk) {
      bkv += v;
      return;
    }
    d[p] -= v;
    while (d[p] <= 0) {
      if (nx[p] == nx[nx[p]]) {
        bkv = bkv - d[p];
        bk = p;
        fa[nx[p]] = nx[p] - 1;
        d[p] = 0, nx[p] = p;
        break;
      }
      d[p] += d[nx[p]];
      fa[nx[p]] = nx[p] - 1;
      nx[p] = nx[nx[p]];
    }
  }
  ll query() { return bkv; }
};


void mian() {
  int n, m;
  std::cin >> n >> m, ++n;
  std::vector<std::vector<std::pair<int, int>>> lf(n + 1);
  while (m--) {
    int l, r, v;
    std::cin >> l >> r >> v;
    lf[r + 1].push_back({l + 1, v});
  }
  std::vector<ll> dp(n + 1, -1e18);
  dp[0] = 0;
  std::vector<ll> ans;
  for (int i = 1; i < n; i++) {
    auto tmp = dp;
    dp.assign(n + 1, -1e18);
    hope h(tmp[0]);
    for (int j = 1; j <= n; j++) {
      for (auto [l, v] : lf[j]) {
        h.add(l - 1, v);
      }
      dp[j] = h.query();
      h.push_back(tmp[j]);
    }
    ans.push_back(dp.back());
  }
  std::reverse(ans.begin(), ans.end());
  for (auto i : ans) std::cout << i << ' ';
  std::cout << '\n';
}
int main() { 
  std::cin.tie(0)->sync_with_stdio(0); 
  int t;
  std::cin >> t;
  while (t--) mian();
}
/*
1 2
4 4

*/