#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
const int MAXP = MAXN * 20;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int pcnt;
array<int, 4> p[MAXN];
vector<pii> g[MAXP];

int dsc[MAXN], dcnt = 0;

int pt[MAXN];
#define lowbit(x) ((x)&-(x))
void insert(int x, int u) {
    x = upper_bound(dsc + 1, dsc + dcnt + 1, x) - dsc - 1;

    while (x <= dcnt) {
        if (pt[x]) {
            g[++pcnt] = {{pt[x], 0}, {u, 0}};
            pt[x] = pcnt;
        } else
            pt[x] = u;

        x += lowbit(x);
    }
}
void query(int x, int u) {
    x = upper_bound(dsc + 1, dsc + dcnt + 1, x) - dsc - 1;

    while (x) {
        if (pt[x])
            g[u].emplace_back(pt[x], 0);

        x ^= lowbit(x);
    }
}

int main(void) {
    int d, n;
    scanf("%d%d", &d, &n);

    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d%d", &p[i][0], &p[i][1], &p[i][2], &p[i][3]);

    int S = 2 * n + 1, T = 2 * n + 2;
    pcnt = T;
    vector< array<int, 4>> vec;

    for (int i = 1; i <= n; ++i) {
        g[i].emplace_back(i + n, p[i][3]);

        if (p[i][1] == 1)
            g[S].emplace_back(i, 0);

        if (p[i][2] == d)
            g[i + n].emplace_back(T, 0);

        vec.push_back({p[i][2] + 1 - p[i][0], 1, p[i][2] + 1 + p[i][0], i + n});
        vec.push_back({p[i][1] - p[i][0], 0, p[i][1] + p[i][0], i});

        dsc[++dcnt] = p[i][1] + p[i][0];
    }

    sort(dsc + 1, dsc + dcnt + 1);
    dcnt = unique(dsc + 1, dsc + dcnt + 1) - dsc - 1;

    sort(vec.begin(), vec.end());

    for (auto t : vec) {
        if (t[1] == 0)
            insert(t[2], t[3]);
        else
            query(t[2], t[3]);
    }

    static ll dis[MAXP];
    static bool vis[MAXP];
    priority_queue< pair<ll, int>> q;
    memset(dis, 0x3f, sizeof(dis));
    dis[S] = 0;
    q.emplace(0, S);

    while (q.size()) {
        int u = q.top().second;
        q.pop();

        if (vis[u])
            continue;

        vis[u] = 1;

        for (auto it : g[u]) {
            int v = it.first;
            ll nxt = dis[u] + it.second;

            if (nxt < dis[v])
                dis[v] = nxt, q.emplace(-dis[v], v);
        }
    }

    if (dis[T] == linf)
        printf("-1");
    else
        printf("%lld", dis[T]);

    return 0;
}