n, m = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(m)]

main_items = []

# 处理主件和附件
for v, p, q in items:
    if q == 0:
        main_items.append({'v': v, 'p': p, 'attachments': []})
    else:
        # 所属主件的编号是q，现在要找到对应的main_items中的索引
        master_idx = q - 1
        if 0 <= master_idx < len(main_items):
            main_items[master_idx]['attachments'].append((v, p))

# 生成每个主件的附件组合
groups = []
for master in main_items:
    mv = master['v']
    mp = master['p']
    atts = master['attachments']
    k = len(atts)
    combinations = []
    for mask in range(0, 1 << k):
        cost = mv
        value = mv * mp
        for i in range(k):
            if mask & (1 << i):
                av, ap = atts[i]
                cost += av
                value += av * ap
        combinations.append((cost, value))
    groups.append(combinations)

# 动态规划处理分组背包
dp = [0] * (n + 1)
for group in groups:
    for j in range(n, -1, -1):
        current_max = dp[j]
        for cost, value in group:
            if j >= cost:
                current_max = max(current_max, dp[j - cost] + value)
        dp[j] = current_max

print(max(dp))
/**************************************************************
	Problem: 2265
	User: admin
	Language: Python
	Result: Wrong Answer
****************************************************************/