#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1e18;
#define X first
#define Y second
int n, m;
vector<ii> P;
vector<ii> G[3000007];
ll dist[3000007];
bool comp_point(int a, int b) {
return P[a] < P[b];
}
int add_point(int x, int y) {
P.emplace_back(x, y);
return P.size() - 1;
}
int cnt = 0;
void add_edges(vector<int> &F, vector<int> &T) {
if(F.empty() || T.empty())
return ;
vector<int> all;
int i = 0, j = 0;
while(i < F.size() || j < T.size()) {
if(i < F.size() && (j == T.size() || P[F[i]] < P[T[j]])) {
all.push_back(F[i]);
i++;
} else {
all.push_back(T[j]);
j++;
}
}
int xmid = P[all[(all.size() - 1) / 2]].X;
//~ for(int x : F) cout << P[x].X << "," << P[x].Y << " "; cout << endl;
//~ for(int x : T) cout << P[x].X << "," << P[x].Y << " "; cout << endl;
//~ cout << xmid << endl << endl;
vector<int> F1, F2;
vector<int> T1, T2;
vector<ii> M;
for(int i : F) {
if(P[i].X <= xmid) {
if(P[i].X < xmid)
F1.push_back(i);
int hlp = add_point(xmid, P[i].Y);
M.push_back({P[i].Y, hlp});
G[i].emplace_back(hlp, 0);
} else
F2.push_back(i);
}
for(int i : T) {
if(P[i].X >= xmid) {
if(P[i].X > xmid)
T2.push_back(i);
int hlp = add_point(xmid, P[i].Y);
M.push_back({P[i].Y, hlp});
G[hlp].emplace_back(i, 0);
} else
T1.push_back(i);
}
sort(M.begin(), M.end(), greater<ii>());
for(int i = 0 ; i + 1 < M.size() ; i++) {
G[M[i].Y].emplace_back(M[i + 1].Y, 0);
if(M[i].X == M[i + 1].X)
G[M[i + 1].Y].emplace_back(M[i].Y, 0);
}
add_edges(F1, T1);
add_edges(F2, T2);
}
ll dijkstra() {
ll res = INF;
set<pll> S;
for(int i = 0 ; i < P.size() ; i++) {
if(P[i].Y - P[i].X == 0) {
dist[i] = 0;
S.insert({0, i});
} else
dist[i] = INF;
}
while(!S.empty()) {
auto p = *(S.begin());
S.erase(S.begin());
for(auto p2 : G[p.Y]) {
if(dist[p2.X] > p.X + p2.Y) {
S.erase({dist[p2.X], p2.X});
dist[p2.X] = p.X + p2.Y;
S.insert({dist[p2.X], p2.X});
}
}
}
for(int i = 0 ; i < P.size() ; i++)
if(P[i].Y - P[i].X == n * 2)
res = min(res, dist[i]);
return res;
}
int main() {
scanf("%d%d", &n, &m);
vector<int> F, T;
for(int i = 0 ; i < m ; i++) {
int t, l, r, c;
scanf("%d%d%d%d", &t, &l, &r, &c);
l--;
F.push_back(add_point(t - r, t + r));
T.push_back(add_point(t - l, t + l));
G[T.back()].emplace_back(F.back(), c);
}
sort(F.begin(), F.end(), comp_point);
sort(T.begin(), T.end(), comp_point);
add_edges(F, T);
ll hlp;
printf("%lld\n", (hlp = dijkstra()) == INF ? -1 : hlp);
return 0;
}
