#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll N, M, sz;
pair<ll, pair<pii, ll>> arr[100005];
vector<pii> graph[100005];
ll seg[200505 * 2];
void update(int pos, ll v) {
pos += sz;
seg[pos] = min(seg[pos], v);
for (; pos > 0; pos >>= 1) seg[pos >> 1] = min(seg[pos], seg[pos ^ 1]);
return;
}
ll query(int l, int r) {
r++;
ll ret = inf;
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret = min(ret, seg[l++]);
if (r & 1) ret = min(ret, seg[--r]);
}
return ret;
}
void Dijkstra(int S, vector<ll> &dist) {
priority_queue<pii, vector<pii>, greater<>> pq;
dist[S] = 0;
pq.push({0, S});
while (pq.size()) {
pii t = pq.top();
pq.pop();
ll now = t.second, v = t.first;
if (dist[now] < v) continue;
for (auto &[next, cost]: graph[now]) {
ll ncost = v + cost;
if (dist[next] > ncost) {
dist[next] = ncost;
pq.push({ncost, next});
}
}
}
}
void subtask_1() {
vector<ll> v;
v.push_back(0);
v.push_back(1), v.push_back(N);
for (int i = 0; i < M; i++) {
v.push_back(arr[i].second.first.first);
v.push_back(arr[i].second.first.second);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
sz = v.size();
sort(arr, arr + M, [&](pair<ll, pair<pii, ll>> a, pair<ll, pair<pii, ll>> b) {
return a.second.first.second < b.second.first.second;
});
for (int i = 0; i < M; i++) {
ll L = arr[i].second.first.first, R = arr[i].second.first.second;
L = lower_bound(v.begin(), v.end(), L) - v.begin();
R = lower_bound(v.begin(), v.end(), R) - v.begin();
arr[i].second.first = {L, R};
}
vector<ll> dp(sz + 5, inf);
memset(seg, 0x3f, sizeof(seg));
dp[0] = 0;
update(0, dp[0]);
for (int i = 0; i < M; i++) {
ll l = arr[i].second.first.first, r = arr[i].second.first.second, c = arr[i].second.second;
ll idx = lower_bound(v.begin(), v.end(), v[l] - 1) - v.begin();
dp[r] = min(dp[r], query(idx, r) + c);
update(r, dp[r]);
}
int idx = lower_bound(v.begin(), v.end(), N) - v.begin();
if (dp[idx] == inf) cout << -1;
else cout << dp[idx];
return;
}
void subtask_2() {
ll ans = inf;
sort(arr, arr + M);
for (int i = 0; i < (1 << M); i++) {
vector<int> v;
ll cost = 0;
for (int j = 0; j < M; j++) {
if (i & (1 << j)) v.push_back(j), cost += arr[j].second.second;
}
vector<pair<pii, ll>> now;
now.push_back({{1, N}, 0});
for (int j: v) {
vector<pair<pii, ll>> nxt;
ll T = arr[j].first, L = arr[j].second.first.first, R = arr[j].second.first.second;
for (auto &[range, t]: now) {
ll l = range.first, r = range.second;
l -= T - t, l = max(l, 1LL);
r += T - t, r = min(r, N);
if (l < L) nxt.push_back({{l, min(r, L - 1)}, T});
if (r > R) nxt.push_back({{max(l, R + 1), r}, T});
}
swap(nxt, now);
}
if (now.empty()) ans = min(ans, cost);
}
if (ans == inf) cout << -1;
else cout << ans;
return;
}
void subtask_3() {
int S = M, E = M + 1;
sort(arr, arr + M);
for (int i = 0; i < M; i++) {
ll t1 = arr[i].first, l1 = arr[i].second.first.first, r1 = arr[i].second.first.second, c1 = arr[i].second.second;
if (l1 == 1) {
graph[S].push_back({i, c1});
graph[i].push_back({S, c1});
}
if (r1 == N) {
graph[E].push_back({i, c1});
graph[i].push_back({E, c1});
}
for (int j = i + 1; j < M; j++) {
ll t2 = arr[j].first, l2 = arr[j].second.first.first, r2 = arr[j].second.first.second, c2 = arr[j].second.second;
ll diff = t2 - t1;
ll a = l1 + diff, b = r1 - diff;
if (a > b) continue;
if (b > r2) {
swap(a, l2);
swap(b, r2);
}
if (b + 1 >= l2) {
graph[i].push_back({j, c2});
graph[j].push_back({i, c2});
}
}
}
vector<ll> dist(N + 5, inf);
Dijkstra(S, dist);
if (dist[E] == inf) cout << -1;
else cout << dist[E];
return;
}
void solve() {
cin >> N >> M;
int sub_task1 = 1, sub_task2 = (M <= 16), sub_task3 = (M <= 5000);
for (int i = 0; i < M; i++) {
ll T, L, R, C;
cin >> T >> L >> R >> C;
if (T != 1) sub_task1 = 0;
arr[i] = {T, {{L, R}, C}};
}
if (sub_task1) {
subtask_1();
return;
}
if (sub_task2) {
//subtask_2();
//return;
}
if (sub_task3) {
subtask_3();
return;
}
return;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
