#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fi first
#define se second
#define _UN using namespace
using namespace std;
typedef pair<int,int> pii;
typedef __int128 i128;
const int MAXN=1e4+10; const long NINF=0xc0c0c0c0c0c0c0c0;
int n,m; long ans[MAXN];
struct Itv{ int l,r,a; } A[MAXN];
vector<Itv> vec[MAXN];
struct DSU{
    int fa[MAXN];
    void init(){ iota(fa,fa+n+1,0); }
    int find(int u){ return fa[u]==u?u:fa[u]=find(fa[u]); }
    void merge(int u,int v){
        if((u=find(u))!=(v=find(v))) fa[v]=u;
    }
} dsu;
long F[MAXN],G[MAXN],D[MAXN];
int nxt[MAXN];
void case_main(){
    cin>>n>>m,n++;
    RNG(i,1,n) vec[i].clear();
    RNG(i,1,m) cin>>A[i].l>>A[i].r>>A[i].a,A[i].l++,A[i].r++,vec[A[i].r].push_back(A[i]);
    auto upd=[](int i,int a){
        i=dsu.find(i);
        D[i]+=a;
        while(nxt[i]&&D[i]+G[i]>G[nxt[i]]) D[i]+=D[nxt[i]],dsu.merge(i,nxt[i]),nxt[i]=nxt[nxt[i]];
    };
    fill(F,F+n+1,NINF),F[0]=0;
    RNG(k,1,n-1){
        copy(F,F+n+1,G); fill(D,D+n+1,0); F[0]=NINF;
        dsu.init();
        RNG(i,1,n){
            for(auto x:vec[i]) upd(x.l-1,x.a);
            int j=dsu.find(i-1);
            F[i]=G[j]+D[j];
            if(G[j]+D[j]>G[i]) dsu.merge(j,i);
            else nxt[j]=i;
        }
        ans[k]=F[n];
    }
    RNG(k,1,n-1) cout<<ans[n-k]<<" ";
    cout<<"\n";
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
//  freopen("yesterday.in","r",stdin);
//  freopen("yesterday.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int cas; cin>>cas;
    RNG(_,1,cas) case_main();
}