#include<bits/stdc++.h>
#include<iomanip>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<stack>
#include<algorithm>
#include<vector>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define inf 100000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x)
#define putl_(x) printf("%lld ",x)
#define get(x) x=read()
#define putl(x) printf("%lld\n",x)
#define rep(p,n,i) for(int i=p;i<=n;i+=1)
#define fep(n,p,i) for(int i=n;i>=p;--i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define pii pair<int,int>
#define mk make_pair
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define uint unsigned long long
#define ui unsigned
#define sq sqrt	
#define x(w) t[w].x
#define r(w) t[w].r
#define l(w) t[w].l
#define sum(w) t[w].sum
#define sc(A) scanf("%d",&A)
#define scl(A) scanf("%lld",&A)	
#define scs(A) scanf("%s",A)
#define put(A) printf("%d\n",A)
#define min(x,y) (x>=y?y:x)
#define max(x,y) (x>=y?x:y)
#define sub(x,y) (x-y<0?x-y+mod:x-y)
using namespace std;
#define mod 998244353
const int MAXN=10010;
int n,m;
int T,len;
struct wy
{
    int l,r,v;
}t[MAXN];
int lin[MAXN],ver[MAXN],nex[MAXN],e[MAXN];
int cmp(wy a,wy b){return a.r==b.r?a.l<b.l:a.r<b.r;}
void add(int x,int y,int z)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
    e[len]=z;
}
//f[i][j]表示前i个点放了j个空边的最大价值。
//f[i][j]=max(f[k][j-1])//钦定第k个位置到k-1位置为空边。
//那么对于li-i这种边代价为1-li均加vi
ll ans[MAXN];
ll f[2][MAXN];
ll g[MAXN],c[MAXN],v[MAXN];
int F[MAXN],L[MAXN],R[MAXN];
int getfather(int x){return x==F[x]?x:F[x]=getfather(F[x]);}
void cle()
{
    ans[0]=0;
    rep(1,n,i)
    {
        g[i]=0;
        ans[i]=0;
        lin[i]=0;
    }
    len=0;
}
void merge(int x,int y)// x>y
{
    int xx=getfather(x);
    int yy=getfather(y);
    if(c[xx]<=c[yy])
    {
        F[xx]=yy;
        R[yy]=R[xx];
    }
}
int main()
{
 //   freopen("1.in","r",stdin);
    sc(T);
    while(T--)
    {
        cle();
        sc(n);sc(m);
        rep(1,m,i)
        {
            sc(t[i].l);
            sc(t[i].r);
            sc(t[i].v);
            ans[0]+=t[i].v;
            g[t[i].l]+=t[i].v;
        }
        sort(t+1,t+1+m,cmp);
        int cnt=1;
        rep(2,m,i)
        {
            if(t[i].l==t[cnt].l&&t[i].r==t[cnt].r)t[cnt].v+=t[i].v;
            else t[++cnt]=t[i];
        }
        rep(1,cnt,i)add(t[i].r,t[i].l,t[i].v);
        fep(n,1,i)g[i]+=g[i+1];
        
        //put(cnt);

        int now=0;ll vv=0;
        rep(1,n,i)
        {
            while(now+1<=cnt&&t[now+1].r<=i-1)
            {
                ++now;
                vv+=t[now].v;
            }
            f[0][i]=vv;
            ans[1]=max(ans[1],f[0][i]+g[i]);
            //cout<<i<<' '<<' '<<now<<' '<<vv<<' '<<g[i]<<endl;
        }
        rep(2,n,j)
        {
            rep(j-1,j-1,i)
            {
                F[i]=L[i]=R[i]=i;
                c[i]=f[j&1][i];
                v[i]=0;
                //merge(i,L[i]-1);
            }
            rep(j,n,i)
            {
                for(int ww=lin[i-1];ww;ww=nex[ww])
                {
                    int tn=ver[ww];
                    if(tn>=j-1)
                    {
                        int xx=getfather(tn);
                        v[xx]+=e[ww];
                        while(R[xx]+1<=i-1)
                        {
                            int yy=getfather(R[xx]+1);
                            if(c[xx]+v[xx]>=c[yy])
                            {
                                R[xx]=R[yy];
                                F[yy]=xx;
                                v[xx]+=v[yy];
                            }
                            else break;
                        }
                    }
                }
                int xx=getfather(i-1);
                f[(j&1)^1][i]=c[xx]+v[xx];
                //cout<<j<<' '<<i<<' '<<f[(j&1)^1][i]<<endl;
                ans[j]=max(ans[j],f[(j&1)^1][i]+g[i]);
                F[i]=L[i]=R[i]=i;
                c[i]=f[j&1][i];
                v[i]=0;
                xx=getfather(L[i]-1);
                if(c[xx]+v[xx]>=c[i])
                {
                    R[xx]=R[i];
                    F[i]=xx;
                }

            }
        }
        rep(1,n-1,i)putl_(ans[n-i]);
        putl(ans[0]);
    }
    return 0;
}