#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<int,2> pr;
const ll MAXN = 1e4+10,INF = 1e18;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
//
int T,n,m; ll ans[MAXN],F[MAXN],G[MAXN];
vector<pr> o[MAXN];

ll w[MAXN];

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)o[i].clear();
    for(int i=1,l,r,v;i<=m;i++){
        cin>>l>>r>>v;
        l++; 
        o[r].push_back((pr){l,v});
    }
    //calc d = 0 ~ n-1
    fill(F,F+n+1,0);
    for(int d=0;d<n;d++){
        fill(w,w+n+1,0); fill(G,G+n+1,0);
        for(int i=0;i<d;i++)G[i] = -INF;
        for(int i=d;i<=n;i++){     
            if(i)G[i] = F[i-1];
            for(auto [l,v] : o[i])for(int j=0;j<l;j++)w[j] += v;
            for(int j=0;j<i;j++)tomax(G[i],G[j] + w[j]);
        }
        ans[n-d] = G[n];
        memcpy(F,G,sizeof F);
    }
    //
    for(int i=1;i<=n;i++)cout<<ans[i]<<" "; cout<<"\n";
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>T;
    while(T--)solve();

    return 0;
}