def main():
    # 读取背包的最大容量 m 和物品总数 n
    m, n = map(int, input().split())
    co = [0]  # 用于记录每个组的起始位置
    C = []
    # 读取每个物品的重量 a、价值 b 和组号 c
    items = []
    for i in range(n):
        a, b, c = map(int, input().split())
        items.append((a, b, c))  # 物品的重量、价值和组号
        C.append(c)
    # 确保物品按组号排序
    items = sorted(items, key=lambda x: x[2])
    flag = 0
    while flag < len(C):
        count = 1
        while flag + 1 < len(C) and C[flag] == C[flag + 1]:
            count += 1
            flag += 1
        co.append(co[-1] + count)
        flag += 1
    # 初始化dp数组
    dp = [[0 for _ in range(m + 1)] for _ in range(len(co))]
    # 动态规划的状态转移
    for i in range(1, len(co)):
        for k in range(m + 1):
            # 对当前组内的每个物品进行检查
            for j in range(co[i - 1], co[i]):
                weight, value, _ = items[j]
                if weight <= k:
                    dp[i][k] = max(dp[i][k], dp[i - 1][k - weight] + value)
            dp[i][k]=max(dp[i][k],dp[i-1][k])
            # 如果当前组没有可选物品，则保留上一组的状态
            if dp[i][k] == 0:
                dp[i][k] = dp[i - 1][k]
    print(dp[len(co) - 1][m])
main()