/*
Ben Watson
Quang Minh MasterDDDDD
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const string name = "test";
void solve();
signed main()
{
if (fopen((name + ".inp").c_str(), "r"))
{
freopen((name + ".inp").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}
// main program
const ll oo = 0x3f3f3f3f3f3f3f;
const int maxm = 1e5 + 1;
int T[maxm], L[maxm], R[maxm], C[maxm];
vector<pair<int, int>> proc;
vector<ll> dist(maxm, oo);
pair<int, int> arr[maxm];
int n, m;
struct Node
{
vector<pair<int, int>> v;
int ptr;
Node() : ptr(0) {};
Node(pair<int, int> val) { v.push_back(val); ptr = 0; }
Node operator + (const Node& other)
{
Node res;
res.v.resize(v.size() + other.v.size());
merge(v.begin(), v.end(), other.v.begin(), other.v.end(), res.v.begin());
return res;
}
};
vector<Node> st;
void build(int head, int l, int r)
{
if (l == r)
{
st[head] = Node(arr[l]);
return;
}
int mid = l + r >> 1;
build(head << 1, l, mid);
build(head << 1 | 1, mid + 1, r);
st[head] = st[head << 1] + st[head << 1 | 1];
}
queue<int> pending;
void perform(int head, int l, int r, int u, int v, int i)
{
if (l > v || r < u) return;
if (u <= l && r <= v)
{
int &cur = st[head].ptr;
while (cur < (int)st[head].v.size())
{
int val = st[head].v[cur].first;
if (val > R[i] + T[i])
break;
int nxt = st[head].v[cur].second;
if (dist[nxt] == oo)
{
pending.push(nxt);
dist[nxt] = dist[i] + C[nxt];
}
cur++;
}
return;
}
int mid = l + r >> 1;
perform(head << 1, l, mid, u, v, i);
perform(head << 1 | 1, mid + 1, r, u, v, i);
}
void perform(int u, int v, int i) { perform(1, 1, m, u, v, i); }
void build()
{
sort(proc.begin(), proc.end());
for (int i = 1; i <= m; i++)
{
int idx = proc[i - 1].second;
arr[i] = {L[idx] + T[idx] - 1, idx};
}
st.resize(4 * m + 1);
build(1, 1, m);
}
void Dijkstra()
{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
for (int i = 1; i <= m; i++)
if (L[i] == 1)
pq.push({dist[i] = C[i], i});
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
int pos = upper_bound(proc.begin(), proc.end(), make_pair(R[u] - T[u], (int)1e9)) - proc.begin();
if (pos != 0)
{
perform(1, pos, u);
while (!pending.empty())
{
int v = pending.front();
pending.pop();
pq.push({dist[v], v});
}
}
}
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> T[i] >> L[i] >> R[i] >> C[i];
proc.push_back({L[i] - T[i] - 1, i});
}
build();
ll res = oo;
Dijkstra();
for (int i = 1; i <= m; i++)
if (R[i] == n)
res = min(res, dist[i]);
cout << (res == oo ? -1 : res) << '\n';
}
