#include <iostream>
#include <vector>

using namespace std;

const int N = 110, M = 200010;

int f[N][M];

struct item
{
    int value;
    int weight;
    int flag; //0表示父
    vector<int> son;
} list[N];

int main()
{
    int n, size;

    cin >> size >> n;
    for (int i = 1; i <= n; i++)
    {
        int q;
        cin >> list[i].weight >> list[i].value >> q;
        list[i].flag = q;
        if (q)
            list[q].son.push_back(i);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!list[i].flag)
        { //附件不能单独考虑,只有主件买了才能买附件
            for (int j = 0; j <= size; j++)
            {
                f[i][j] = f[i - 1][j];
                int w = list[i].weight;
                if (j >= w)
                {
                    f[i][j] = max(f[i][j], f[i - 1][j - w] + list[i].value * list[i].weight);
                    int son_n = list[i].son.size();
                    for (int k = 0; k < (1 << son_n - 1); k++)
                    { //枚举每个子集的方案
                        int new_w, new_val;
                        for (int bit = 0; bit < son_n; bit++)
                        {
                            if (k >> bit & 1)
                            {

                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}