#include<iostream>
#include<algorithm>
#define mn 4010
#define FOR(i,x,y) for(int i=x;i<=y;++i)
#define ROF(i,x,y) for(int i=x;i;--i)
using namespace std;
int n,m,cnt;
int a[mn],b[mn];
int c[mn],d[mn];
int g[55][mn];
int f[55][55][mn];
int zzz[55][55][mn];
int pre[55][55][mn];
int ans[55];
void calc(int l,int r,int k)
{
	if(l>r)return;
	int pos=zzz[l][r][k=pre[l][r][k]];
	ans[pos]=d[k];
	calc(l,pos-1,k);
	calc(pos+1,r,k);
}
int main()
{
	ios::sync_with_stdio(false); 
	cin>>n>>m;
	FOR(i,1,m)cin>>a[i]>>b[i]>>c[i],d[i]=c[i];
	sort(d+1,d+m+1);
	cnt=unique(d+1,d+m+1)-d-1;
	FOR(i,1,m)c[i]=lower_bound(d+1,d+cnt+1,c[i])-d;
	ROF(l,n,0)
	{
		FOR(r,l,n)
		{
			FOR(mid,l,r)FOR(k,0,cnt)g[mid][k]=0;
			FOR(i,1,m)if(l<=a[i]&&b[i]<=r)FOR(mid,a[i],b[i])g[mid][c[i]]++;
			FOR(mid,l,r)ROF(k,cnt-1,0)g[mid][k]+=g[mid][k+1];
			ROF(k,cnt,0)
			{
				int res=0;
				FOR(mid,l,r)
				{
					int tmp=f[l][r][k]=max(f[l][r][k],f[l][mid-1][k]+f[mid+1][r][k]+g[mid][k]*d[k]);
                    if(tmp>=res)res=tmp,zzz[l][r][k]=mid;
				}
				if(f[l][r][k+1]<=res)f[l][r][k]=res,pre[l][r][k]=k;
				else f[l][r][k]=f[l][r][k+1],pre[l][r][k]=pre[l][r][k+1];
			}
		}
	}
	cout<<f[1][n][1]<<'\n';
	calc(1,n,1);
	FOR(i,1,n)cout<<ans[i]<<' ';
	return 0;
}