// Not afraid to dark.

#include <bits/stdc++.h>
using namespace std;

clock_t start_time, end_time;
#define GET_START start_time = clock ();
#define GET_END end_time = clock (); fprintf (stderr, "TIME COSSEMED : %0.3lf\n", 1.0 * (end_time - start_time) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))

#define ll long long

namespace io {
    int read_pos, read_dt; char read_char;
    inline int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    inline void write (ll x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
}

const int N = 1e4;
int n, m;
ll f[N + 5], ans[N + 5];
struct node {
    int l, r, v;
    inline node (){
        l = r = v = 0;
    }
    inline void read (){
        io::read (l), io::read (r), io::read (v);
    }
};
vector < node > tl[N + 5];

int fa[N + 5], rep[N + 5], cnt[N + 5];

int find (int v){
    if (fa[v] == v)
        return fa[v];
    return fa[v] = find (fa[v]);
}

inline void Merge (int u, int v){
    u = find (u), v = find (v);
    if (cnt[u] < cnt[v])
        swap (u, v);
    if (u != v){
        fa[v] = u;
        rep[u] = min (rep[u], rep[v]);
        cnt[u] += cnt[v];
    }
}

struct ty {
    int pre, nex;
    ll delta, cc;
    ty (){
        pre = 0, nex = n + 1, delta = 0, cc = 0;
    }
} te[N + 5];

inline void Addty (int u, int v, int i){
    te[u].nex = te[v].pre = i;
    te[i].pre = u, te[i].nex = v;
    te[u].cc = f[i] - f[u];
    te[i].cc = f[v] - f[i];
}
inline void Delty (int i){
    static int u, v;
    u = te[i].pre, v = te[i].nex;
    te[u].delta += te[i].delta;
    te[u].cc += te[i].cc;
    te[u].nex = v;
    te[v].pre = u;
}

int CNT, tg;
inline void ARKNIGHTS (){
    ++ CNT;
    io::read (n), io::read (m);
    if (CNT == 4)
        printf ("%d %d\n", n, m);
    for (int i = 1;i <= n;++ i)
        tl[i].clear ();
    for (int i = 1;i <= m;++ i){
        node t; t.read ();
        if (CNT == 4)
            printf ("%d %d %d\n", t.l, t.r, t.v);
        ++ t.l;
        tl[t.r].push_back (t);
    }
    for (int i = 1;i <= n;++ i){
        f[i] = f[i - 1];
        for (auto x : tl[i])
            f[i] += x.v;
    }
    ans[n] = f[n], ans[0] = 0;
    for (int t = 1;t < n;++ t){
        for (int i = n;i > 0;-- i)
            f[i] = f[i - 1];
        for (int i = 0;i <= n + 1;++ i)
            te[i] = ty ();
        cnt[t] = 1, fa[t] = t, rep[t] = t;
        Addty (0, n + 1, t);
        for (int i = t + 1, las;i <= n;++ i){
            for (auto x : tl[i])
                if (x.l - 1 >= t){
                    int u = rep[find (x.l - 1)];
                    te[u].delta += x.v;
                    while (te[u].nex != n + 1 && te[u].delta >= te[u].cc){
                        Merge (u, te[u].nex);
                        Delty (te[u].nex);
                    }
                }
            cnt[i] = 1, fa[i] = i, rep[i] = i;
            las = te[n + 1].pre;
            if (f[i] <= f[las] + te[las].delta){
                f[i] = f[las] + te[las].delta;
                Merge (las, i);
            } else
                Addty (las, n + 1, i);
        }
        ans[n - t] = f[n];
    }
    if (tg){
        for (int i = 1;i <= n;++ i)
            io::write (ans[i]), putchar (' '); puts ("");
    }
}

signed main (){
    GET_START

    int TT = io::read ();
    if (TT == 2)
        tg = 1;
    for (int T = TT;T --;)
        ARKNIGHTS ();

    GET_END
    return 0;
}