import java.util.*;

// 定义物品类
class Goods {
    int v; // 价格
    int degree; // 满意度
    boolean isMain = false; // 是否为主件

    int a1 = -1; // 附件1的编号
    int a2 = -1; // 附件2的编号
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        // 标准输入
        Scanner input = new Scanner(System.in);
        // 获取总金额和商品总个数
        int money = input.nextInt();
        int count = input.nextInt();
        // 初始化物品列表
        List<Goods> list = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            Goods goods = new Goods();
            list.add(goods);
        }
        // 初始化列表数据
        for (int i = 0; i < count; i++) {
            Goods goods = list.get(i);
            int v = input.nextInt();
            int p = input.nextInt();
            int q = input.nextInt();
            // 设置物品属性
            goods.v = v;
            goods.degree = v * p;
            if (q == 0) {
                goods.isMain = true; // 当前物品为主键
            } else if (list.get(q-1).a1 == -1) {
                // 在其对应主件中记录此附件
                list.get(q-1).a1 = i;
            } else {
                list.get(q-1).a2 = i;
            }        
        } // 列表数据初始化完成

        // 初始化动态规划矩阵
        int [][] dp = new int[count+1][money+1];
        // 将矩阵第一行和第一列填充为0，但其默认值已为0，无需再处理

        // 遍历矩阵，进行动态规划
        for (int i = 1; i <= count; i++) {
            // 获取当前物品信息
            Goods curGoods = list.get(i-1);
            int curV = curGoods.v;
            int curD = curGoods.degree;
            // 当前物品是否存在附件
            boolean has_a1 = curGoods.a1 != -1 ? true : false;
            boolean has_a2 = curGoods.a2 != -1 ? true : false;
            // 当前物品的附件
            Goods a1 = has_a1 ? list.get(curGoods.a1) : null;
            Goods a2 = has_a2 ? list.get(curGoods.a2) : null;
        
            for (int j = 1; j <= money; j++) {
                // 预处理,保底填充上行数据
                dp[i][j] = dp[i-1][j];
                if (!curGoods.isMain) {
                    // 当前物品不为主件
                    continue;
                } else { // 当前物品为主件时，对应4种选择
                    
                    // 1.只选择主件
                    if (j >= curV) {
                        dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i-1][j - curV] + curD
                        );
                    }

                    // 2.选择主件和附件1
                    if ( has_a1 && j >= (curV + a1.v) ) {
                        // 状态转移
                        dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i-1][j-curV-a1.v] + curD + a1.degree
                        );
                    }

                    // 3.选择主件和附件2
                    if ( has_a2 && j >= (curV + a2.v) ) {
                        // 状态转移
                        dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i-1][j-curV-a2.v] + curD + a2.degree
                        );
                    }

                    // 4.选择主件、附件1和附件2
                    if (has_a1 && has_a2 && j >= (curV + a1.v + a2.v) ) {
                        // 状态转移
                        dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i-1][j-curV-a1.v-a2.v] + curD + a1.degree + a2.degree
                        );
                    }
                }
            }
        } // 填充矩阵完毕

        // 输出动态规划结果
        System.out.println(dp[count][money]);
    }
}