#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using llu=unsigned long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

const int NV=1e4;

namespace ufs{
    int f[NV+5];
    void init(int n){
        for(int i=0;i<=n;++i) f[i]=i;
    }int fd(int x){
        return x==f[x]?x:f[x]=fd(f[x]);
    }
}

namespace xm{
    std::vector<std::pair<int,int> > seg[NV+5];
    ll f[NV+5],pf[NV+5],z[NV+5],ans[NV+5];
    int to[NV+5];
    void add(int i,int w,int R){
        z[i]+=w;
        while(to[i]<R&&z[i]>f[to[i]]-f[i]){
            ufs::f[to[i]]=i;
            z[i]+=z[to[i]];
            to[i]=to[to[i]];
        }
    }void _(){
        int N,M;

        scanf("%d%d",&N,&M);

        for(int i=1;i<=N;++i) seg[i].clear();
        memset(f,0,sizeof*f*(N+1));
        memset(pf,0,sizeof*pf*(N+1));
        memset(ans,0,sizeof*ans*(N+1));

        for(int i=1;i<=M;++i){
            int l,r,w;
            scanf("%d%d%d",&l,&r,&w);
            seg[r].emplace_back(l,w);
        }
        for(int d=0;d<N;++d){
            ufs::init(N);
            for(int i=0;i<=N;++i){
                pf[i]=f[i];
                f[i]=-(1ll<<61);
                z[i]=0;
                to[i]=i+1;
            }
            f[d]=0;
            for(int i=d+1;i<=N;++i){
                for(auto s:seg[i]) if(s.fi>=d) add(ufs::fd(s.fi),s.se,i);
                f[i]=max(pf[i-1],f[ufs::fd(i-1)]+z[ufs::fd(i-1)]);
                cmax(ans[i-d],f[i]);
            }
        }
        for(int i=1;i<=N;++i){
            cmax(ans[i],ans[i-1]);
            printf("%llfpd ",ans[i]);
        }
        puts("");
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--) xm::_();
    return 0;
}