#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
const ll inf = 1e17 + 5;
const int nmax = 3e5 + 33;
#define left deobiceicineintreabasussy
#define right deobiceicineintreababaka
struct AINT {
struct node {
int pri;
ll mn, val;
int area;
node *l, *r;
int ind() {
return l -> area + 1;
}
} *nil = new node{-1, inf, inf, 0, 0, 0};
using ns = node*;
struct pns {
ns l, r;
};
ns updnode(ns nde, ns x, int val) {
(val? nde -> r : nde -> l) = x;
nde -> area = nde -> l -> area + nde -> r -> area + 1;
nde -> mn = min({nde -> l -> mn, nde -> r -> mn, nde -> val});
return nde;
}
ns merge(ns l, ns r) {
return l == nil? r:
r == nil? l:
l -> pri > r -> pri? updnode(l, merge(l -> r, r), 1):
updnode(r, merge(l, r -> l), 0);
}
pns split(ns x, int val) {
pns temp;
return val == 0? pns{nil, x}:
x -> area <= val? pns{x, nil}:
x -> ind() <= val? (temp = split(x -> r, val - x -> ind()), temp.l = updnode(x, temp.l, 1), temp):
(temp = split(x -> l, val), temp.r = updnode(x, temp.r, 0), temp);
}
ns root = nil;
void append() {
root = merge(root, new node{abs((int)rand()), inf, inf, 1, nil, nil});
}
ll query(int l, int r) {
pns temp[2] = {split(root, l - 1), split(temp[0].r, r - l + 1)};
ll rez = temp[1].l -> mn;
root = merge(temp[0].l, merge(temp[1].l, temp[1].r));
return rez;
}
void upd(int poz, ll val) {
pns temp[2] = {split(root, poz - 1), split(temp[0].r, 1)};
temp[1].l -> val = min(temp[1].l -> val, val);
temp[1].l -> mn = temp[1].l -> val;
root = merge(temp[0].l, merge(temp[1].l, temp[1].r));
return;
}
};
AINT left, right;
#define norm deobiceicineintreaba
map<int,int> norm;
signed main() {
srand(time(0));
cin >> m >> n;
vector<tuple<int,int,int,ll> > v(m);
for(auto &[a, b, c, d] : v) {
cin >> a >> b >> c >> d;
norm[a];
norm[b];
norm[c];
}
norm[1];
norm[n];
int cnt = 1;
for(auto &x : norm)
x.second = cnt++;
n = cnt - 1;
for(int i = 1; i <= n; i++) {
left.append();
right.append();
}
left.upd(1, 0);
right.upd(n, 0);
ll minn = inf;
bool ok = 0;
for(auto [a, b, c, d] : v) {
a = norm[a];
b = norm[b];
c = norm[c];
ll l = left.query(a, b), r = right.query(a, b);
//cout << l << ' ' << r << '\n';
if(minn > l + r + d)
minn = l + r + d, ok = 1;
left.upd(c, l + d);
right.upd(c, r + d);
}
if(!ok)
cout << -1 << '\n';
else
cout << minn << '\n';
}
