#include <stdio.h>

#define N 61

int n,m;

int dp[3202];

int v[N],w[N],d[N];

bool f[3202][N];

FILE *in,*out;

int main()

{

in = fopen("budget.in","r");

out = fopen("budget.out","w");

int i ,j ,k;

fscanf(in,"%d %d",&m,&n);

m = m / 10;

for (i = 1;i <= n ;i ++)

{

fscanf(in,"%d%d%d",&w[i],&j,&d[i]);

w[i] /= 10;

v[i] = w[i] * j * 10;

}

for (i = 1;i <= n;i ++)

for (j = m;j >= w[i]; j --)

{

if ((dp[j - w[i]] + v[i] > dp[j]) && (!d[i] || f[j - w[i]][d[i]]))

{

dp[j] = dp[j - w[i]] + v[i];

for (k = 1; k < i ; k ++)

f[j][k] = f[j - w[i]][k];

f[j][i] = true;

}

}

fprintf(out,"%d\n",dp[m]);

for (i = 1 ;i <= n ;i ++)

if (f[m][i])

fprintf(out,"%d ",i);

fclose(in);

fclose(out);

return 0;

}