#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long//_______________________________________________________________________________________
#define file(name) if(fopen(name".inp","r")) {freopen(name".inp", "r",stdin); freopen(name".out","w",stdout);}//
#define all(x, y) (x).begin() + 1, (x).begin() + (y) + 1 //
#define All(x) (x).begin(), (x).end() //
#define el cerr<<'\n'; //
#define debug(x) cerr << #x << " = " << x << '\n' //
#define sevpts signed main //
#define vl vector<int> //
#define pii pair<int, int> //
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i) //
#define FOD(i,a,b) for (int i=(a); i>=(b); --i) //
#define REP(i,n) for (int i = 0; i < (n); ++i) //
#define pb push_back //
#define fi first// __ //
#define se second// <(o )____ //
const int MOD2 = 988244353;// ( ._> / //
const int MOD = 1e9 + 7;// `----' //
const long long INF = 2 * 1e9; //
const int maxn = 5e5 + 69; //
const int maxn2 = 1e3 + 69; //
//____________________________________________________________________________________________________________//
int n;
struct seg {
vl st;
vl lazy;
int n;
seg (int sz) {
n = sz;
st.assign(4*n, INF);
lazy.assign(4*n, INF);
}
void down (int id) {
int val = lazy[id];
lazy[2*id] = min(lazy[2*id], val);
lazy[2*id + 1] = min(lazy[2*id + 1], val);
st[2*id] = min(st[2*id], val);
st[2*id + 1] = min(st[2*id + 1], val);
lazy[id] = INF;
}
void build (int id, int l, int r, vl & a) {
if (l == r)
st[id] = a[l];
else {
int mid = l + r >> 1;
build(2*id, l, mid, a);
build(2*id + 1, mid+ 1, r, a);
}
}
void build (vl & a) {
build(1,1,n,a);
}
void upd (int id, int l, int r, int u, int v, int val) {
if(r < u || l > v)
return;
if (u <= l && r <= v) {
lazy[id] = min(lazy[id], val);
st[id] = min(st[id], val);
}
else {
int mid = l + r >> 1;
down(id);
upd(2*id, l, mid, u, v, val);
upd(2*id + 1, mid + 1, r, u, v, val);
}
}
void upd(int u, int v, int val) {
upd(1,1,n,u,v,val);
}
ll get (int id, int l, int r, int i) {
if ( i == 0) return 0;
if (l == r) return st[id];
else {
down(id);
int mid = l + r >> 1;
if(i <= mid) {
return get(2*id, l, mid, i);
}
return get(2*id + 1, mid + 1, r ,i);
}
}
ll get (int i) {
return get(1,1,n,i);
}
};
struct query {
ll L, R, C;
};
void sibidi() {
int n, q;
cin >> n >> q;
vl dp(maxn);
fill(All(dp), INF);
seg tree(n);
tree.build(dp);
vector< query > Q(maxn);
FOR(i,1,q) cin >> Q[i].L >> Q[i].R >> Q[i].C;
sort(all(Q,q), [] (const query & a, const query & b) {
return a.L < b.L;
});
FOR(i,1,q) {
ll l = Q[i].L, r = Q[i].R, c = Q[i].C;
int val = min(tree.get(r), tree.get(l-1) + c);
tree.upd(l, r, val);
// debug(i);
// debug(val);
// FOR(j,1,n) cerr<<tree.get(j)<<" ";
// el;
// el;
}
if(tree.get(n) == INF) cout<< -1;
else
cout<<tree.get(n);
}
sevpts(){
// file("");
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt--)
sibidi();
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgbGwgbG9uZyBsb25nLy9fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KI2RlZmluZSBmaWxlKG5hbWUpIGlmKGZvcGVuKG5hbWUiLmlucCIsInIiKSkge2ZyZW9wZW4obmFtZSIuaW5wIiwgInIiLHN0ZGluKTsgZnJlb3BlbihuYW1lIi5vdXQiLCJ3IixzdGRvdXQpO30vLwojZGVmaW5lIGFsbCh4LCB5KSAoeCkuYmVnaW4oKSArIDEsICh4KS5iZWdpbigpICsgKHkpICsgMSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vCiNkZWZpbmUgQWxsKHgpICh4KS5iZWdpbigpLCAoeCkuZW5kKCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLwojZGVmaW5lIGVsIGNlcnI8PCdcbic7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vCiNkZWZpbmUgZGVidWcoeCkgY2VyciA8PCAjeCA8PCAiID0gIiA8PCB4IDw8ICdcbicgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy8KI2RlZmluZSBzZXZwdHMgc2lnbmVkIG1haW4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLwojZGVmaW5lIHZsIHZlY3RvcjxpbnQ+ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLwojZGVmaW5lIHBpaSBwYWlyPGludCwgaW50PiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy8KI2RlZmluZSBGT1IoaSxhLGIpICBmb3IgKGludCBpPShhKTsgaTw9KGIpOyArK2kpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLwojZGVmaW5lIEZPRChpLGEsYikgZm9yIChpbnQgaT0oYSk7IGk+PShiKTsgLS1pKSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vCiNkZWZpbmUgUkVQKGksbikgZm9yIChpbnQgaSA9IDA7IGkgPCAobik7ICsraSkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy8KI2RlZmluZSBwYiBwdXNoX2JhY2sgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLwojZGVmaW5lIGZpIGZpcnN0Ly8gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgX18gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vCiNkZWZpbmUgc2Ugc2Vjb25kLy8gICAgICAgICAgICAgICAgICAgICAgICAgICAgPChvIClfX19fICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy8KY29uc3QgaW50IE1PRDIgPSA5ODgyNDQzNTM7Ly8gICAgICAgICAgICAgICAgICAgICggIC5fPiAvICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLwpjb25zdCBpbnQgTU9EID0gMWU5ICsgNzsvLyAgICAgICAgICAgICAgICAgICAgICAgIGAtLS0tJyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vCmNvbnN0IGxvbmcgbG9uZyBJTkYgPSAyICogMWU5OyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLwpjb25zdCBpbnQgbWF4biA9IDVlNSArIDY5OyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vCmNvbnN0IGludCBtYXhuMiA9IDFlMyArIDY5OyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy8KLy9fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18vLwoKaW50IG47CnN0cnVjdCBzZWcgewogICAgdmwgc3Q7CiAgICB2bCBsYXp5OwogICAgaW50IG47CgogICAgc2VnIChpbnQgc3opIHsKICAgICAgICBuID0gc3o7CiAgICAgICAgc3QuYXNzaWduKDQqbiwgSU5GKTsKICAgICAgICBsYXp5LmFzc2lnbig0Km4sIElORik7CiAgICB9CgogICAgdm9pZCBkb3duIChpbnQgaWQpIHsKICAgICAgICBpbnQgdmFsID0gbGF6eVtpZF07CgogICAgICAgIGxhenlbMippZF0gPSBtaW4obGF6eVsyKmlkXSwgdmFsKTsKICAgICAgICBsYXp5WzIqaWQgKyAxXSA9IG1pbihsYXp5WzIqaWQgKyAxXSwgdmFsKTsKICAgICAgICBzdFsyKmlkXSA9IG1pbihzdFsyKmlkXSwgdmFsKTsKICAgICAgICBzdFsyKmlkICsgMV0gPSBtaW4oc3RbMippZCArIDFdLCB2YWwpOwogICAgICAgIGxhenlbaWRdID0gSU5GOwogICAgfQoKICAgIHZvaWQgYnVpbGQgKGludCBpZCwgaW50IGwsIGludCByLCB2bCAmIGEpIHsKICAgICAgICBpZiAobCA9PSByKQogICAgICAgICAgICBzdFtpZF0gPSBhW2xdOwogICAgICAgIGVsc2UgewogICAgICAgICAgICBpbnQgbWlkID0gbCArIHIgPj4gMTsKICAgICAgICAgICAgYnVpbGQoMippZCwgbCwgbWlkLCBhKTsKICAgICAgICAgICAgYnVpbGQoMippZCArIDEsIG1pZCsgMSwgciwgYSk7CiAgICAgICAgfQogICAgfQogICAgdm9pZCBidWlsZCAodmwgJiBhKSB7CiAgICAgICAgYnVpbGQoMSwxLG4sYSk7CiAgICB9CgoKICAgIHZvaWQgdXBkIChpbnQgaWQsIGludCBsLCBpbnQgciwgaW50IHUsIGludCB2LCBpbnQgdmFsKSB7CiAgICAgICAgaWYociA8IHUgfHwgbCA+IHYpCiAgICAgICAgICAgIHJldHVybjsKCiAgICAgICAgaWYgKHUgPD0gbCAmJiByIDw9IHYpIHsKICAgICAgICAgICAgbGF6eVtpZF0gPSBtaW4obGF6eVtpZF0sIHZhbCk7CiAgICAgICAgICAgIHN0W2lkXSA9IG1pbihzdFtpZF0sIHZhbCk7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBpbnQgbWlkID0gbCArIHIgPj4gMTsKICAgICAgICAgICAgZG93bihpZCk7CiAgICAgICAgICAgIHVwZCgyKmlkLCBsLCBtaWQsIHUsIHYsIHZhbCk7CiAgICAgICAgICAgIHVwZCgyKmlkICsgMSwgbWlkICsgMSwgciwgdSwgdiwgdmFsKTsKICAgICAgICB9CiAgICB9CiAgICB2b2lkIHVwZChpbnQgdSwgaW50IHYsIGludCB2YWwpIHsKICAgICAgICB1cGQoMSwxLG4sdSx2LHZhbCk7CiAgICB9CgoKICAgIGxsIGdldCAoaW50IGlkLCBpbnQgbCwgaW50IHIsIGludCBpKSB7CiAgICAgICAgaWYgKCBpID09IDApIHJldHVybiAwOwogICAgICAgIGlmIChsID09IHIpIHJldHVybiBzdFtpZF07CiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIGRvd24oaWQpOwogICAgICAgICAgICBpbnQgbWlkID0gbCArIHIgPj4gMTsKICAgICAgICAgICAgaWYoaSA8PSBtaWQpIHsKICAgICAgICAgICAgICAgIHJldHVybiBnZXQoMippZCwgbCwgbWlkLCBpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICByZXR1cm4gZ2V0KDIqaWQgKyAxLCBtaWQgKyAxLCByICxpKTsKICAgICAgICB9CiAgICB9CiAgICBsbCBnZXQgKGludCBpKSB7CiAgICAgICAgcmV0dXJuIGdldCgxLDEsbixpKTsKICAgIH0KfTsKCnN0cnVjdCBxdWVyeSB7CiAgICBsbCBMLCBSLCBDOwp9OwoKdm9pZCBzaWJpZGkoKSB7CiAgICBpbnQgbiwgcTsKICAgIGNpbiA+PiBuID4+IHE7CiAgICB2bCBkcChtYXhuKTsKICAgIGZpbGwoQWxsKGRwKSwgSU5GKTsKICAgIHNlZyB0cmVlKG4pOwogICAgdHJlZS5idWlsZChkcCk7CiAgICB2ZWN0b3I8IHF1ZXJ5ID4gUShtYXhuKTsKICAgIEZPUihpLDEscSkgY2luID4+IFFbaV0uTCA+PiBRW2ldLlIgPj4gUVtpXS5DOwogICAgc29ydChhbGwoUSxxKSwgW10gKGNvbnN0IHF1ZXJ5ICYgYSwgY29uc3QgcXVlcnkgJiBiKSB7CiAgICAgICAgcmV0dXJuIGEuTCA8IGIuTDsKICAgIH0pOwogICAgRk9SKGksMSxxKSB7CiAgICAgICAgbGwgbCA9IFFbaV0uTCwgciA9IFFbaV0uUiwgYyA9IFFbaV0uQzsKICAgICAgICBpbnQgdmFsID0gbWluKHRyZWUuZ2V0KHIpLCB0cmVlLmdldChsLTEpICsgYyk7CiAgICAgICAgdHJlZS51cGQobCwgciwgdmFsKTsKICAgICAgICAvLyBkZWJ1ZyhpKTsKICAgICAgICAvLyBkZWJ1Zyh2YWwpOwogICAgICAgIC8vIEZPUihqLDEsbikgY2Vycjw8dHJlZS5nZXQoaik8PCIgIjsKICAgICAgICAvLyBlbDsKICAgICAgICAvLyBlbDsKCiAgICB9CiAgICBpZih0cmVlLmdldChuKSA9PSBJTkYpIGNvdXQ8PCAtMTsKICAgIGVsc2UgCiAgICAgICAgY291dDw8dHJlZS5nZXQobik7Cgp9CgpzZXZwdHMoKXsKICAgIC8vIGZpbGUoIiIpOwogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwogICAgY291dC50aWUobnVsbHB0cik7CiAgICBpbnQgdHQgPSAxOwogICAgLy9jaW4gPj4gdHQ7CiAgICB3aGlsZSh0dC0tKQogICAgc2liaWRpKCk7CiAgICByZXR1cm4gMDsKfQoK