#include <iostream>

using namespace std;
// group数组索引代表组号，值代表组内物品数量
int group[1005];
// row代表组号，col代表组内物品编号,weight代表重量，value代表价值
int weight[1005][1005];
int value[1005][1005];
int total_group;
int total_item;
int total_room;
int dp[1005];

int main()
{
    cin >> total_room >> total_item;
    for (int i = 0; i < total_item; i++)
    {
        int temp_weight, temp_value, temp_group;
        cin >> temp_weight >> temp_value >> temp_group;
        group[temp_group]++;
        total_group = max(total_group, temp_group);
        weight[temp_group][group[temp_group]] = temp_weight;
        value[temp_group][group[temp_group]] = temp_value;
    }
    for (int i = 0; i < total_group; i++)
    {
        for (int k = total_room; k >= 0; k--)
        {
            for (int j = 1; j <= group[i]; j++)
            {
                if (k >= weight[i][j])
                {
                    dp[k] = max(dp[k], dp[k - weight[i][j]] + value[i][j]);
                }
            }
        }
    }
    cout << dp[total_room] << endl;
    return 0;
}