#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
il void cmax(ll &x,ll y){x=x>y?x:y;}
il void swap(int &x,int &y){int z=x;x=y,y=z;}
const int N=10005;const ll inf=1e18;
int T,n,m,fa[N],nxt[N];ll f[N],g[N],v[N],ans[N],d[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
il void Union(int x,int y){
    x=find(x),y=find(y);if(x!=y) fa[y]=x;
}

vector<pii> e[N];
int x,y,z,u;ll w;
int main(){
    //freopen("qoj7905_0.in","r",stdin);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;++i) e[i].clear(),ans[i]=0;
        for(int i=1;i<=m;++i) scanf("%d%d%d",&x,&y,&z),e[y].push_back({x,z});
        for(int i=0;i<=n;++i) f[i]=0;
        for(int tt=0;tt<n;++tt){
            for(int i=tt;i<=n;++i) g[i]=f[i],f[i]=0,v[i]=0;
            for(int i=tt;i<=n;++i) fa[i]=i,nxt[i]=0;w=0ll;
            for(int i=tt+1;i<=n;++i){
                f[i]=g[i-1];
                for(auto it:e[i]){
                    if(it.fi<tt) continue;
                    x=find(it.fi),v[x]+=1ll*it.se;
                    while(nxt[x] && f[x]+v[x]>=f[nxt[x]]) f[x]+=v[nxt[x]],fa[nxt[x]]=x,nxt[x]=nxt[nxt[x]];
                    //for(int j=tt;j<=it.fi;++j) v[j]+=1ll*it.se;

                }
                //for(int j=tt;j<i;++j) cmax(f[i],v[j]);
                cmax(f[i],f[find(i-1)]+v[find(i-1)]);
                if(f[i]>w) fa[i]=i,nxt[find(i-1)]=i;
                else fa[i]=find(i-1);
            }
            for(int i=tt+1;i<=n;++i) cmax(ans[i-tt],f[i]);
        }
        for(int i=1;i<=n;++i) printf("%lld%c",ans[i],i==n?'\n':' ');
    }

    return 0;
}