//f[i][j]:前i个血量为j时的最大高度

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e2 + 10;

int f[N][3000+10], n, m,res;
struct node {
    int t;
    int v;
    int h;
}a[N];

bool cmp(node x, node y)
{
    return x.t < y.t;
}
int main()
{
    cin >> n >> m;
    memset(f, -1, sizeof f);
    for (int i = 1; i <= m; i++) {
        cin >> a[i].t >> a[i].v >> a[i].h;
    }
    sort(a + 1, a + m + 1, cmp);
    f[0][10] = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= 3000; j++) {
            int tem = a[i].t - a[i - 1].t;
            if (j+tem >=a[i].v&& j + tem - a[i].v<=3000&& f[i - 1][j + tem - a[i].v]>=0) {
                f[i][j] = max(f[i][j], f[i - 1][j + tem - a[i].v]);
            }
            if (j+tem>=0&&j+tem<=3000&& f[i - 1][j + tem]>=0) {
                f[i][j] = max(f[i][j], f[i - 1][j + tem] + a[i].h);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= 3000; j++) {
            if (f[i][j] >= 0) {
                res = max(res, a[i].t);
            }
            if (f[i][j] >= n) {
                cout << a[i].t << endl;

                return 0;
            }
        }
    }
    cout << res << endl;

    return 0;
}