#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#define int ll
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define ff first
#define ss second
const int MAXM = 1e5 + 7;
ll dp[MAXM];
int n;
bool inter(int b, int a2, int d, int d2) {
int r = abs(d - d2);
return (b + 1) - r >= a2;
}
const int base = 1 << 18;
vector<pair<int, int>> tree[2 * base]; //{y, nr}
void add(int x, int y, int nr) {
x += base;
tree[x].push_back({y, nr});
}
void build(int v) {
if (v >= base) {
sort(tree[v].begin(), tree[v].end(), [&](pii a, pii b){return a.ff > b.ff;});
if (tree[v].empty()) return;
return;
}
build(v * 2);
build(v * 2 + 1);
vector<pii> tab1 = tree[v * 2];
vector<pii> tab2 = tree[v * 2 + 1];
reverse(tab1.begin(), tab1.end());
reverse(tab2.begin(), tab2.end());
while (tab1.size() && tab2.size()) {
if (tab1.back().ff > tab2.back().ff) {
tree[v].push_back(tab1.back());
tab1.pop_back();
}
else {
tree[v].push_back(tab2.back());
tab2.pop_back();
}
}
if (tab1.size()) for (auto & val : tab1) tree[v].push_back(val);
if (tab2.size()) for (auto & val : tab2) tree[v].push_back(val);
if (tree[v].empty()) return;
}
vector<int> query(int x, int y) {
vector<int> punkty;
int l = 1 + base - 1;
int r = x + base + 1;
while (l / 2 != r / 2) {
if (l % 2 == 0) {
while (tree[l + 1].size()) {
if (dp[tree[l + 1].back().ss] != 1e18) tree[l + 1].pop_back();
else if (tree[l + 1].back().ff <= y) {
punkty.push_back(tree[l + 1].back().ss);
tree[l + 1].pop_back();
}
else break;
}
}
if (r % 2 == 1) {
while (tree[r - 1].size()) {
if (dp[tree[r - 1].back().ss] != 1e18) tree[r - 1].pop_back();
else if (tree[r - 1].back().ff <= y) {
punkty.push_back(tree[r - 1].back().ss);
tree[r - 1].pop_back();
}
else break;
}
}
l /= 2;
r /= 2;
}
return punkty;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int m, a, b, c, d;
cin >> n >> m;
map<int, int> skalax;
map<int, int> skalay;
vector<pair<pii, pii>> tab;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c >> d;
tab.push_back({{b, c}, {a, d}});
skalax[c + a + 1] = 0;
skalax[b + a] = 0;
skalay[b - a] = 0;
skalay[c + 1 - a] = 0;
//cout << c + a + 1 << ' ' << c + 1 - a << ' ' << b + a << ' ' << b - a << '\n';
}
int wsk = 1;
for (auto & [k, v] : skalax) {
v = wsk++;
}
wsk = 1;
for (auto & [k, v] : skalay) {
v = wsk++;
}
priority_queue<pii, vector<pii>, greater<pii>> kolejka;
for (int i = 0; i < m; i++) {
dp[i] = 1e18;
if (tab[i].ff.ff == 1) {
dp[i] = tab[i].ss.ss;
kolejka.push({tab[i].ss.ss, i});
}
else {
add(skalax[tab[i].ff.ff + tab[i].ss.ff], skalay[tab[i].ff.ff - tab[i].ss.ff], i);
}
}
ll ans = 1e18;
build(1);
while (!kolejka.empty()) {
int v = kolejka.top().ss;
int c = kolejka.top().ff;
// cout << v << ' ' << c << '\n';
if (tab[v].ff.ss == n) ans = min(ans, dp[v]);
kolejka.pop();
vector<int> t = query(skalax[tab[v].ff.ss + tab[v].ss.ff + 1], skalay[tab[v].ff.ss + 1 - tab[v].ss.ff]);
for (int j : t){
//cout << v << ": " << j << '\n';
if (dp[j] != 1e18) continue;
dp[j] = dp[v] + tab[j].ss.ss;
kolejka.push({dp[j], j});
}
}
if (ans == 1e18) ans = -1;
cout << ans << '\n';
return 0;
}
