#include<bits/stdc++.h>
using namespace std;
int n,m;
#define ll long long
#define mp make_pair
#define pi pair<int,int>
#define pb push_back
#define fi first
#define se second
vector<pi>g[10100];
const ll I=1e18;
ll dp[10100],dp2[10100],ans[10010],all,cf[10100];
int nx[10100],fa[10100],pr[10100];
int F(int x){if(x==fa[x])return x;return fa[x]=F(fa[x]);}
void del(int x,int io){
    int a=pr[x],b=nx[x];nx[a]=b,pr[b]=a;
    cf[b]+=cf[x];
    if(b==io)all-=cf[x];
    fa[x+1]=F(x);
}
void sol(){
    scanf("%d%d",&n,&m);n++;
    for(int i=1;i<=n+3;i++)g[i].clear();
    for(int i=1,l,r,z;i<=m;i++)scanf("%d%d%d",&l,&r,&z),l+=2,r+=2,g[r].pb(mp(l,z));
    dp[1]=0;
    for(int i=2;i<=n+1;i++)dp[i]=-I;
    for(int e=1;e<n;e++){
        all=0;
        dp[0]=0;
        for(int i=1;i<=n+1;i++)nx[i]=i+1,pr[i]=i-1,cf[i]=dp[i]-dp[i-1];
        pr[n+2]=n+1,nx[0]=1;
        for(int i=1;i<=n+3;i++)fa[i]=i;
        for(int i=1;i<=n+1;i++){
            if(i>1){
                all+=cf[i-1];
                if(pr[i-1]==0||cf[i-1]>=0);
                else del(i-1,i);
            }
            dp2[i]=-I;
            for(auto it:g[i]){
                int z=F(it.fi)-1;
                if(!z)continue;
                z=nx[z];
                cf[nx[0]]+=it.se;
                if(z<i){
                    cf[z]-=it.se;
                    while(z<i&&cf[z]<0){
                        int v=nx[z];
                        del(z,i),z=v;
                    }
                }
                else all+=it.se;
            }
            if(pr[i])dp2[i]=max(dp2[i],all);
        }
        for(int i=1;i<=n+1;i++)dp[i]=dp2[i];
        ans[n-e]=dp[n+1];
    }
    for(int i=1;i<n;i++)printf("%lld ",ans[i]);puts("");
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}