//典型的背包问题01 
// 但是又附加条件及附件的购买
//前面选择会影响后面，要标记 
#include<stdio.h>
int a[100][8]={0};//自己，等级，子件数，子1，2 
int b[100][10005]={0};
int main()
{
	int i,j,k,n,m,q,w,e,l,max;
	scanf("%d%d",&n,&m);
	j=1;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&q,&w,&e);
		if(e==0)
		{
			a[j][0]=q;
			a[j][1]=w;
			a[j][2]=e;
			j++;
		}
		else
		{
			a[e][2]++;
			a[e][2+a[e][2]*2-1]=q;
			a[e][2+a[e][2]*2]=w;
		}
	}
	k=j-1;
	for(i=1;i<=k;i++)
	{
		for(j=1;j<=n;j++)
		{
			b[i][j]=b[i-1][j];
			if(b[i-1][j-a[i][0]]+a[i][1]*a[i][0]>b[i][j]&&j-a[i][0]>=0)
			{
				b[i][j]=b[i-1][j-a[i][0]]+a[i][1]*a[i][0];
			}
			if(b[i-1][j-a[i][0]-a[i][3]]+a[i][1]*a[i][0]+a[i][4]*a[i][3]>b[i][j]&&j-a[i][0]-a[i][3]>=0&&a[i][2]>=1)
				b[i][j]=b[i-1][j-a[i][0]-a[i][3]]+a[i][1]*a[i][0]+a[i][4]*a[i][3];
			if(b[i-1][j-a[i][0]-a[i][5]]+a[i][1]*a[i][0]+a[i][6]*a[i][5]>b[i][j]&&j-a[i][0]-a[i][5]>=0&&a[i][2]==2)
				b[i][j]=b[i-1][j-a[i][0]-a[i][3]-a[i][5]]+a[i][1]*a[i][0]+a[i][6]*a[i][5];
			if(b[i-1][j-a[i][0]-a[i][3]-a[i][5]]+a[i][1]*a[i][0]+a[i][4]*a[i][3]+a[i][6]*a[i][5]>b[i][j]&&j-a[i][0]-a[i][3]-a[i][5]>=0&&a[i][2]==2)
				b[i][j]=b[i-1][j-a[i][0]-a[i][3]-a[i][5]]+a[i][1]*a[i][0]+a[i][4]*a[i][3]+a[i][6]*a[i][5];
		}
	}
	for(i=1;i<=k;i++)
	{
		for(j=0;j<=6;j++)
		{
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
	for(i=1;i<=k;i++)
	{
		for(j=100;j<=n;j=j+100)
		{
			printf("%d ",b[i][j]);
		}
		printf("\n");
	}
	printf("%d",b[k][n]);
 }