#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX_N = 10000 + 5;
const ll INF64 = 1e18;

int N, M, l[MAX_N], r[MAX_N], val[MAX_N], fath[MAX_N];
ll suml[MAX_N], tot, f[MAX_N], ans[MAX_N];
vector <pair <int, int>> rightp[MAX_N];
struct Node{
    int pre, suf;
    ll val, lazy;
    
    void clear() {
        pre = -1;
        suf = -1;
        val = 0;
        lazy = 0;
    }
    
    inline ll operator () () const {return val + lazy;}
}node[MAX_N];
int tl;

int Find(int x) {
    return x == fath[x] ? x : fath[x] = Find(fath[x]);
}

void ins(int i) {
    node[i].pre = tl;
    if (tl != -1) {
        node[tl].suf = i;
    }
    tl = i;
}

void del(int i) {
    if (node[i].pre != -1) {
        node[node[i].pre].suf = node[i].suf;
        node[node[i].pre].lazy += node[i].lazy;
    }
    if (node[i].suf != -1) {
        node[node[i].suf].pre = node[i].pre;
        fath[Find(node[i].suf)] = Find(i);
    }
    node[i].clear();
}

void solve() {
    tot = 0;
    for (int i = 1; i <= N; i ++) {
        suml[i] = 0;
        rightp[i].clear();
    }
    
    cin >> N >> M;
    for (int i = 1; i <= M; i ++) {
        cin >> l[i] >> r[i] >> val[i];
        l[i] ++; tot += val[i]; suml[l[i]] += val[i];
        rightp[r[i]].emplace_back(l[i], val[i]);
    }
    
    ans[N] = tot;
    for (int i = 1; i <= N; i ++) {
        f[i] = INF64;
    }
    f[0] = 0;
    for (int i = 1; i < N; i ++) {
        static ll g[MAX_N];
        for (int j = 0; j <= N; j ++) {
            fath[j] = j;
            node[j].clear();
        }
        tl = -1;
        ll res = INF64;
        node[i - 1].val = f[i - 1];
        ins(i - 1);
        for (int j = i; j <= N; j ++) {
            node[tl].lazy += suml[j];
            g[j] = node[tl]();
            for (auto [lp, v] : rightp[j]) {
                int k = Find(lp - 1);
                if (k >= i - 1) {
                    node[k].lazy -= v;
                    while (node[k].suf != -1 && node[k]() <= node[node[k].suf].val) {
                        del(node[k].suf);
                    }
                }
            }
            if (node[tl]() > f[j]) {
                node[j].val = f[j];
                ins(j);
            }else {
                fath[j] = Find(j - 1);
            }
            res = min(res, g[j]);
        }
        memcpy(f, g, sizeof(ll) * (N + 1));
        ans[N - i] = tot - res;
    }
    
    for (int i = 1; i <= N; i ++) cout << ans[i] << "\n "[i < N];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int T;
    cin >> T;
    while (T --) solve();
    
    return 0;
}