#include<iostream>
#define ll long long
using namespace std;
const int maxn=32005;
ll ww[65],vv[65],p[65];
ll w[65],v[65];
ll c1[65][maxn],c2[65][maxn];
ll dp[maxn],cnt[65];//以容积为数组下标 
ll n,W;
ll ans;
/*
*/
int maxx(int a,int b,int c,int d,int e){
	int ans=a;
	if(b>ans)ans=b;
	if(c>ans)ans=c;
	if(d>ans)ans=d;
	if(e>ans)ans=e;
	return ans;
}
int main(){
	cin>>W>>n;
	for(int i=1;i<=n;i++){
		cin>>ww[i]>>vv[i]>>p[i];
		vv[i]*=ww[i];
		//主附件依赖问题的处理？
		if(p[i]==0){
			c1[i][0]=ww[i];
			c2[i][0]=vv[i];
			continue;
		} 
		cnt[p[i]]++;
		c1[p[i]][cnt[p[i]]]=ww[i];//第几个数的第几个 
		c2[p[i]][cnt[p[i]]]=vv[i];//主件怎么办？ 
	}
	int t=0;
	for(int i=1;i<=n;i++){
		if(cnt[i]==0&&p[i]==0) {//一种情况，只买主件 
			w[++t]=c1[p[i]][0],v[t]=c2[p[i]][0];			
		}
		if(cnt[i]==1){//两种情况，只买主件或主+1副 
			w[++t]=c1[p[i]][0],v[t]=c2[p[i]][0];
			w[++t]=c1[p[i]][1]+w[t-1],v[t]=c2[p[i]][1]+v[t-1];
		}
		if(cnt[i]==2){//三种情况
			w[++t]=c1[p[i]][0],v[t]=c2[p[i]][0];
			w[++t]=c1[p[i]][1]+w[t-1],v[t]=c2[p[i]][1]+v[t-1];
			w[++t]=c1[p[i]][2]+w[t-2],v[t]=c2[p[i]][2]+v[t-2];
			w[++t]=w[t-1]+w[t-2]+w[t-3],v[t]=v[t-1]+v[t-2]+v[t-3];
		}
	}
	for(int i=1;i<=t;i++)
		cout<<v[i]<<" ";
		cout<<endl;
	for(int i=1;i<=t;i++)
		cout<<w[i]<<" ";
		cout<<endl;
	//背包处理 
	for(int i=1;i<=t;i++)
		for(int k=i;k<=i+cnt[i];k++){
			if(p[i]==0)continue;
			for(int  j=W;j>=w[i];j--){
				dp[j]=max(dp[j],dp[j-w[k]]+v[k]);
			}
		}
	cout<<dp[W];
	return 0;
}