rambless

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int N = in.nextInt();
            int m = in.nextInt();

            Goods[] arr = new Goods[m + 1];
            for (int i = 1; i <= m; i++) {
                int v = in.nextInt();
                int p = in.nextInt();
                int q = in.nextInt();
                arr[i] = new Goods(v, p, q);
            }
            for (int i = 1; i < arr.length; i++) {
                if (arr[i].q > 0) {
                    if (arr[arr[i].q].a == 0) {
                        arr[arr[i].q].a = i;
                    } else {
                        arr[arr[i].q].b = i;
                    }
                }
            }

            //构造dp二维数组dp[i][j]，存放j钱数下，买前i种物品的最大满意度
            int[][] dp = new int[m + 1][N + 1];
            for (int i = 1; i <= m; i++) {
                int v0 = 0, z0 = 0;
                int v1 = 0, z1 = 0;
                int v2 = 0, z2 = 0;
                int v3 = 0, z3 = 0;
                if (arr[i].a == 0 && arr[i].b == 0) {
                    v0 = arr[i].v;
                    z0 = arr[i].v * arr[i].p;
                }
                if (arr[i].a != 0 && arr[i].b == 0) {
                    v0 = arr[i].v;
                    z0 = arr[i].v * arr[i].p;
                    v1 = arr[i].v + arr[arr[i].a].v;
                    z1 = arr[i].v * arr[i].p + arr[arr[i].a].v * arr[arr[i].a].p;
                }
                if (arr[i].a == 0 && arr[i].b != 0) {
                    v0 = arr[i].v;
                    z0 = arr[i].v * arr[i].p;
                    v2 = arr[i].v + arr[arr[i].b].v;
                    z2 = arr[i].v * arr[i].p + arr[arr[i].b].v * arr[arr[i].b].p;
                }
                if (arr[i].a != 0 && arr[i].b != 0) {
                    v0 = arr[i].v;
                    z0 = arr[i].v * arr[i].p;
                    v1 = arr[i].v + arr[arr[i].a].v;
                    z1 = arr[i].v * arr[i].p + arr[arr[i].a].v * arr[arr[i].a].p;
                    v2 = arr[i].v + arr[arr[i].b].v;
                    z2 = arr[i].v * arr[i].p + arr[arr[i].b].v * arr[arr[i].b].p;
                    v3 = arr[i].v + arr[arr[i].a].v + arr[arr[i].b].v;
                    z3 = arr[i].v * arr[i].p + arr[arr[i].a].v * arr[arr[i].a].p + arr[arr[i].b].v *
                         arr[arr[i].b].p;
                }
                for (int j = 0; j <= N; j++) {
                    //附件时跳过及非附件时赋初始值
                    dp[i][j] = dp[i - 1][j];
                    if (arr[i].q == 0) {
                        if (j >= v0 && v0 > 0) {
                            dp[i][j] = Math.max(dp[i - 1][j - v0] + z0, dp[i][j]);
                        }
                        if (j >= v1 && v1 > 0) {
                            dp[i][j] = Math.max(dp[i - 1][j - v1] + z1, dp[i][j]);
                        }
                        if (j >= v2 && v2 > 0) {
                            dp[i][j] = Math.max(dp[i - 1][j - v2] + z2, dp[i][j]);
                        }
                        if (j >= v3 && v3 > 0) {
                            dp[i][j] = Math.max(dp[i - 1][j - v3] + z3, dp[i][j]);
                        }
                    }
                }
            }
            System.out.println(dp[m][N]);
        }
    }



    static class Goods {
        public Goods(int v, int p, int q) {
            this.v = v;
            this.p = p;
            this.q = q;
        }
        private int v;
        private int p;
        private int q;

        private int a = 0;//附件1的ID
        private int b = 0;//附件2的ID
    }
}