#include <bits/stdc++.h>

std::vector<int> fa;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

using LL = long long;

void solve() {
  int n, m; scanf("%d %d", &n, &m);
  std::vector<std::vector<std::pair<int, int>>> s(n + 1);
  for (int i = 0, l, r, w; i < m; i++) {
    scanf("%d %d %d", &l, &r, &w);
    s[r].emplace_back(l, w);
  }
  std::vector<LL> ans(n + 1), g(n + 1);
  for (int d = 0; d < n; d++) {
    std::vector<LL> f(n + 1, -1e18), val(n + 1);
    std::vector<int> nxt(n + 1);
    fa.resize(n + 1), std::iota(fa.begin(), fa.end(), 0);
    nxt.resize(n + 1), std::iota(nxt.begin(), nxt.end(), 1);
    auto add = [&](int p, int w, int r) {
      val[p] += w;
      while (nxt[p] < r && val[p] > f[nxt[p]] - f[p])
        fa[nxt[p]] = p, val[p] += val[nxt[p]], nxt[p] = nxt[nxt[p]];
    };
    f[d] = 0;
    for (int i = d + 1; i <= n; i++) {
      for (const auto &[l, w] : s[i]) if (l >= d) 
        add(find(l), w, i);
      f[i] = std::max(g[i - 1], f[find(i - 1)] + val[find(i - 1)]);
      ans[i - d] = std::max(ans[i - d], f[i]);
    }
    g = f;
  }
  for (int i = 1; i <= n; i++) {
    ans[i] = std::max(ans[i], ans[i - 1]);
    printf("%d ", ans[i]);
  }
  printf("\n");
}

int main() {
  int T; scanf("%d", &T); while (T--) {
    solve();
  }
}