int v[M];//体积
int w[M];//价值
int f[2][N][2];//进行了滚动数组优化
//f[i][j][k],前i个物品，体积为j，第i个物品选不选
vector<int>son[M];//记录各个主件的附件
bool flag[M];//标记主件

void solve(int times)
{
    int n,m;cin >> n >> m;
    int fa;
    for(int i = 1;i <= m;i++){
        cin >> v[i] >> w[i] >> fa;

        if(fa == 0){    
            flag[i] = 1;    //标记主件
        }else son[fa].push_back(i);

        w[i] = v[i]*w[i];
    }  

    for(int i = 1;i <= m;i++){  //枚举物品
        for(int j = 0;j <= n;j++){  //枚举体积
            if(!flag[i]){   //不是主件就只能不选当前物品
                f[i%2][j][0] = max(f[(i-1)%2][j][0],f[(i-1)%2][j][1]);
                continue;
            }

            //不选
            f[i%2][j][0] = max(f[(i-1)%2][j][0],f[(i-1)%2][j][1]);
            //只选主件不选附件
            if(j - v[i] >= 0)f[i%2][j][1] = max(f[(i-1)%2][j - v[i]][1],f[(i-1)%2][j - v[i]][0]) + w[i];
            //选一个附件
            if(son[i].size() == 1 && j - v[i] - v[son[i][0]] >= 0)f[i%2][j][1] = max(f[i%2][j][1],max(f[(i-1)%2][j - v[i] - v[son[i][0]]][1],f[(i-1)%2][j - v[i] - v[son[i][0]]][0]) + w[i] + w[son[i][0]]);
            if(son[i].size() == 2 && j - v[i] - v[son[i][1]] >= 0)f[i%2][j][1] = max(f[i%2][j][1],max(f[(i-1)%2][j - v[i] - v[son[i][1]]][1],f[(i-1)%2][j - v[i] - v[son[i][1]]][0]) + w[i] + w[son[i][1]]);
            //选两个附件
            if(son[i].size() == 2 && j - v[i] - v[son[i][1]] - v[son[i][0]] >= 0)f[i%2][j][1] = max(f[i%2][j][1],max(f[(i-1)%2][j - v[i] - v[son[i][0]] - v[son[i][1]]][1],f[(i-1)%2][j - v[i] - v[son[i][0]] - v[son[i][1]]][0]) + w[i] + w[son[i][0]] + w[son[i][1]]);
        }
    }

    cout << max(f[m%2][n][1],f[m%2][n][0]);
}