#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 10;
int n, m;
struct TREAT {
int t, l, r, c;
friend istream& operator >> (istream& is, TREAT& rhs) {
return is >> rhs.t >> rhs.l >> rhs.r >> rhs.c;
}
} treat[N];
vector<int> rrhT{0};
namespace IT {
bool mk[N];
deque<int> f[N << 2], g[N << 2];
void update(int s, int l, int r, int x, int y) {
if (x < l || x > r) return;
f[s].push_back(y);
g[s].push_back(y);
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) update(s << 1, l, mid, x, y);
else update(s << 1 | 1, mid + 1, r, x, y);
}
void build(int s, int l, int r) {
sort(f[s].begin(), f[s].end(), [&](const auto& i, const auto& j) {
return treat[i].l + rrhT[treat[i].t] > treat[j].l + rrhT[treat[j].t];
});
sort(g[s].begin(), g[s].end(), [&](const auto& i, const auto& j) {
return treat[i].l - rrhT[treat[i].t] > treat[j].l - rrhT[treat[j].t];
});
if (l == r) return;
int mid = (l + r) >> 1;
build(s << 1, l, mid);
build(s << 1 | 1, mid + 1, r);
}
vector<int> vt;
void get1(int s, int l, int r, int u, int v, int x) {
if (v < l || u > r || !f[s].size()) return;
if (u <= l && r <= v) {
for (; f[s].size(); f[s].pop_back()) {
int j = f[s].back();
if (!mk[j]) {
if (treat[j].l + rrhT[treat[j].t] > x) break;
vt.push_back(j);
mk[j] = true;
}
}
return;
}
int mid = (l + r) >> 1;
get1(s << 1, l, mid, u, v, x);
get1(s << 1 | 1, mid + 1, r, u, v, x);
}
void get2(int s, int l, int r, int u, int v, int x) {
if (v < l || u > r || !g[s].size()) return;
if (u <= l && r <= v) {
for (; g[s].size(); g[s].pop_back()) {
int j = g[s].back();
if (!mk[j]) {
if (treat[j].l - rrhT[treat[j].t] > x) break;
vt.push_back(j);
mk[j] = true;
}
}
return;
}
int mid = (l + r) >> 1;
get2(s << 1, l, mid, u, v, x);
get2(s << 1 | 1, mid + 1, r, u, v, x);
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) cin >> treat[i];
for (int i = 1; i <= m; ++i) treat[i].l -= 1;
for (int i = 1; i <= m; ++i) rrhT.push_back(treat[i].t);
sort(rrhT.begin(), rrhT.end());
rrhT.erase(unique(rrhT.begin(), rrhT.end()), rrhT.end());
const int sz = rrhT.size() - 1;
for (int i = 1; i <= m; ++i) {
auto& [t, l, r, c] = treat[i];
t = lower_bound(rrhT.begin(), rrhT.end(), t) - rrhT.begin();
IT::update(1, 1, sz, t, i);
}
IT::build(1, 1, sz);
using pii = pair<long long, int>;
priority_queue<pii, vector<pii>, greater<>> q;
for (int i = 1; i <= m; ++i) {
if (!treat[i].l) {
IT::mk[i] = true;
q.push({treat[i].c, i});
}
}
while (q.size()) {
auto [d, u] = q.top(); q.pop();
const auto& [t, l, r, c] = treat[u];
if (r == n) {
cout << d << "\n";
return 0;
}
IT::vt.clear();
IT::get1(1, 1, sz, t, sz, r + rrhT[t]);
IT::get2(1, 1, sz, 1, t, r - rrhT[t]);
for (const auto& j : IT::vt) q.push({d + treat[j].c, j});
}
cout << -1 << "\n";
}
