Language: C++

//#define _AOJ_


        /*vvv>
        zzzzzI
 .---.  zzuzuI                 .vgggg&,.
+++++=  dAC:|I  .WbbWo       JMM9^```?TMB`  ..&gNNg,.   gggggggJ,   qgggggggg] (&&&&&&&&[   c+OA&J,   (&&&&&&+J,   .cJeAA&-.  (&&&&&&&&x   .&AA&=-.
+++++=  dTqk|I  Xpbpbp      JM#`           (M#^   ?MMp  MM|   +TMN. JMF      ' |yk      ` dVY    7Vk,  Vy     XV  cVf     ?Y!  JM         V$      `
+++++=  dcf:|I  Xppppp      dMN           .MM+     .MM  MM|     MM] JMMMMMM+   |@tqkoh)  ,y0      (V$  yyyyyyyV7  VV           JMWyZWr    TWVVVVW&,
++++++  d7qk|0  Xppppp      ^HMN,    _.db  WMm,   .MMF  MM|   ..MM` JMF      . |yk       .WV&.   .XW'  yy   4yn.  jyn      +.  JM                #S
`++++`  ?ZZZX=  ?WWWW=        -THMMMMH9^    (TMMMMM9!   MMMMMMM""   JMMMMMMMME |UU.        ?TUUUUY=    UU.   (UU-  ^7TUUUV7!   JUUUUUUUU  7TUNKO*/

#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
typedef long double ld;
typedef string cs;
typedef vector<lint> liv;
//#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(),v.end()

#define pb push_back
#define _vcppunko4(tuple) _getname4 tuple
#define _getname4(_1,_2,_3,_4,name,...) name
#define _getname3(_1,_2,_3,name,...) name
#define _trep2(tuple) _rep2 tuple
#define _trep3(tuple) _rep3 tuple
#define _trep4(tuple) _rep4 tuple
#define _rep1(n) for(lint i=0;i<n;++i)
#define _rep2(i,n) for(lint i=0;i<n;++i)
#define _rep3(i,a,b) for(lint i=a;i<b;++i)
#define _rep4(i,a,b,c) for(lint i=a;i<b;i+=c)
#define _trrep2(tuple) _rrep2 tuple
#define _trrep3(tuple) _rrep3 tuple
#define _trrep4(tuple) _rrep4 tuple
#define _rrep1(n) for(lint i=n-1;i>=0;--i)
#define _rrep2(i,n) for(lint i=n-1;i>=0;--i)
#define _rrep3(i,a,b) for(lint i=b-1;i>=a;--i)
#define _rrep4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c)
template<class T>
istream& operator>>(istream& is,vector<T>& vec);
template<class T,size_t size>
istream& operator>>(istream& is,array<T,size>& vec);
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p);
template<class T>
ostream& operator<<(ostream& os,vector<T>& vec);
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p);
template<class T>
istream& operator>>(istream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p){ os<<p.first<<" "<<p.second;return os; }

inline void in(){}
template <class Head,class... Tail>
inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); }
inline bool out(){ cout<<'\n';return 0; }
template <class T>
inline bool out(T t){ cout<<t<<'\n';return 0; }
template <class Head,class... Tail>
inline bool out(Head head,Tail... tail){ cout<<head<<' ';out(move(tail)...);return 0; }
inline void ssize(lint s){}
template <class Head,class... Tail>
inline void ssize(lint s,Head&& head,Tail&&... tail){ head.resize(s);ssize(s,move(tail)...); }

#define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__))
#define rrep(...) _vcppunko4((__VA_ARGS__,_trrep4,_trrep3,_trrep2,_rrep1))((__VA_ARGS__))

template<class T>
ostream& operator<<(ostream& os,vector<T>& vec){ os<<vec[0];rep(i,1,vec.size())os<<' '<<vec[i];return os; }
template<class T>
ostream& operator<<(ostream& os,deque<T>& deq){ os<<deq[0];rep(i,1,deq.size())os<<' '<<deq[i];return os; }

#define each(v) for(auto &e:v)
#define lin(...) lint __VA_ARGS__;in(__VA_ARGS__)
#define stin(...) string __VA_ARGS__;in(__VA_ARGS__)
#define vin(type,name,size) vector<type> name(size);in(name)
#define fi e.first
#define se e.second
#define YES(c) cout<<((c)?"YES\n":"NO\n"),0
#define Yes(c) cout<<((c)?"Yes\n":"No\n"),0
#define POSSIBLE(c) cout<<((c)?"POSSIBLE\n":"IMPOSSIBLE\n"),0
#define Possible(c) cout<<((c)?"Possible\n":"Impossible\n"),0
#define o(p) cout<<p<<endl,0
#define sp(p) cout<<p<<" "
#define no(p) cout<<p
#ifdef __ENV_TQK__
#define deb(p) cout<<p<<endl,0
#else
#define deb(p) 0
#endif
#define dd(n) cout<<fixed<<setprecision(n)
//mint
#define md_tmp template<uint_fast64_t md=1000000007>
md_tmp class mint{
	using u64=uint_fast64_t;

public:
	u64 a;

	constexpr mint(const u64 x=0) noexcept: a(x%md){}
	constexpr u64 &value() noexcept{ return a; }
	constexpr const u64 &value() const noexcept{ return a; }
	constexpr mint operator+(const mint rhs) const noexcept{
		return mint(*this)+=rhs;
	}
	constexpr mint operator-(const mint rhs) const noexcept{
		return mint(*this)-=rhs;
	}
	constexpr mint operator*(const mint rhs) const noexcept{
		return mint(*this)*=rhs;
	}
	constexpr mint operator^(const lint rhs) const noexcept{
		return mint(*this)^=rhs;
	}
	constexpr mint operator/(const mint rhs) const noexcept{
		return mint(*this)/=rhs;
	}
	constexpr mint &operator+=(const mint rhs) noexcept{
		a+=rhs.a;
		if(a>=md)a-=md;
		return *this;
	}
	constexpr mint &operator-=(const mint rhs) noexcept{
		if(a<rhs.a)a+=md;
		a-=rhs.a;
		return *this;
	}
	constexpr mint &operator*=(const mint rhs) noexcept{
		a=a*rhs.a%md;
		return *this;
	}
	constexpr mint &operator^=(const lint rhs) noexcept{
		if(!rhs)return *this=1;
		u64 exp=rhs-1;
		mint base=this->a;
		while(exp){
			if(exp&1)*this*=base;
			base*=base;
			exp>>=1;
		}
		return *this;
	}
	constexpr mint &operator/=(const mint rhs) noexcept{
		a=(*this*(rhs^(md-2))).a;
		return *this;
	}
};
md_tmp istream& operator>>(istream& os,mint<md>& m){
	os>>m.a,m.a%=md;
	return os;
}
md_tmp ostream& operator<<(ostream& os,const mint<md>& m){
	return os<<m.a;
}
md_tmp mint<md> ncr(lint n,lint r){
	if(n<r||n<0||r<0)return mint<md>(0);
	mint<md>ncr_res=1,ncr_div=1;
	rep(r)ncr_res*=(n-i),ncr_div*=(r-i);
	return ncr_res/ncr_div;
}
#ifndef _AOJ_
mint<> operator""m(unsigned long long n){ return mint<>(n); }
mint<998244353> operator""m9(unsigned long long n){ return mint<998244353>(n); }
mint<1000003> operator""m3(unsigned long long n){ return mint<1000003>(n); }
#endif
using mi=mint<>;

////P
//class P{ public:lint f,s; constexpr P(lint a,lint b):f(a),s(b){};constexpr P():f(0),s(0){}; };
//istream& operator>>(istream& is,P& p){ is>>p.f>>p.s;return is; }
//ostream& operator<<(ostream& os,const P& p){ return os<<p.f<<" "<<p.s<<endl; }
//bool operator<(const P& l,const P& r){ return(l.f-r.f?l.f<r.f:l.s<r.s); }
//bool operator>(const P& l,const P& r){ return(l.f-r.f?l.f>r.f:l.s>r.s); }
struct C{ lint f,s,t; };
bool operator<(const C& l,const C& r){ return l.t<r.t; }
bool operator>(const C& l,const C& r){ return l.t>r.t; }

//const
#define linf 1152921504606846976
//#define inf linf//INT_MAX
#define MAXN 330
#define md_1e9_7 1000000007
#define md_998244353 998244353
#define pi 3.14159265358979323846
//#define mod md_1e9_7

const int d4[5]={0,1,0,-1,0};

//funcs
#define compare(T,s) [](T l,T r){return(s);}

inline void eraseunique(string &v){//nの変更を忘れるな
	v.erase(unique(all(v)),v.end());
}

template<typename T>
vector<pair<T,lint>> runlength(vector<T> v){
	lint n=v.size();
	vector<pair<T,lint>> ret(1,{v[0],1});
	rep(i,1,n){
		if(ret[ret.size()-1].first==v[i])++ret[ret.size()-1].second;
		else ret.push_back({v[i],1});
	}
	return ret;
}

template<typename T,class F>//ラムダ式の受け取り方
vector<T> ruiseki(vector<T> a,F f,lint e){
	lint n=a.size();
	vector<T> s(n+1);
	rep(n)s[i+1]=f(s[i],a[i]);
	return s;
}

set< lint > divisor(lint n){
	set< lint > ret;
	for(lint i = 1; i * i <= n; i++){
		if(n % i == 0){
			ret.insert(i);
			if(i * i != n) ret.insert(n / i);
		}
	}
	return (ret);
}


//\funcs

// Segment Tree Beats
// - l<=i<r について、 A_i の値を min(A_i, x) に更新
// - l<=i<r について、 A_i の値を max(A_i, x) に更新
// - l<=i<r の中の A_i の最大値を求める
// - l<=i<r の中の A_i の最小値を求める
// - l<=i<r の A_i の和を求める
// - l<=i<r について、 A_i の値に x を加える
// - l<=i<r について、 A_i の値を x に更新

// 各ノードごとに構造体にまとめる形で実装 (このように実装しないとTLEした)
class SegmentTree{
	static const lint inf = linf+10;
	struct Node{
		Node *left,*right;
		lint max_v,smax_v,max_c;
		lint min_v,smin_v,min_c;
		lint sum;
		lint len,ladd,lval;

		Node(): left(0),right(0),ladd(0),lval(inf){}

		void init(lint x){
			max_v = min_v = sum = x;
			smax_v = -inf; smin_v = inf;
			max_c = min_c = 1;
		}

		void init_empty(){
			max_v = smax_v = -inf;
			min_v = smin_v = inf;
			max_c = min_c = 0;
		}

		void update_max(lint x){
			sum += (x - max_v) * max_c;

			if(max_v == min_v){
				max_v = min_v = x;
			} else if(max_v == smin_v){
				max_v = smin_v = x;
			} else{
				max_v = x;
			}

			if(lval != inf && x < lval){
				lval = x;
			}
		}

		void update_min(lint x){
			sum += (x - min_v) * min_c;

			if(max_v == min_v){
				max_v = min_v = x;
			} else if(max_v == smin_v){
				min_v = smax_v = x;
			} else{
				min_v = x;
			}

			if(lval != inf && lval < x){
				lval = x;
			}
		}

		void addalint(lint x){
			max_v += x;
			if(smax_v != -inf) smax_v += x;
			min_v += x;
			if(smin_v != inf) smin_v += x;

			sum += len * x;
			if(lval != inf){
				lval += x;
			} else{
				ladd += x;
			}
		}

		void updatealint(lint x){
			max_v = min_v = x;
			smax_v = -inf; smin_v = inf;
			max_c = min_c = len;

			sum = len * x;
			lval = x; ladd = 0;
		}

		void push(){

			if(lval != inf){
				left->updatealint(lval);
				right->updatealint(lval);
				lval = inf;
				return;
			}

			if(ladd != 0){
				left->addalint(ladd);
				right->addalint(ladd);
				ladd = 0;
			}

			if(max_v < left->max_v){
				left->update_max(max_v);
			}
			if(left->min_v < min_v){
				left->update_min(min_v);
			}

			if(max_v < right->max_v){
				right->update_max(max_v);
			}
			if(right->min_v < min_v){
				right->update_min(min_v);
			}
		}

		void update(){
			sum = left->sum + right->sum;

			if(left->max_v < right->max_v){
				max_v = right->max_v;
				max_c = right->max_c;
				smax_v = max(left->max_v,right->smax_v);
			} else if(left->max_v > right->max_v){
				max_v = left->max_v;
				max_c = left->max_c;
				smax_v = max(left->smax_v,right->max_v);
			} else{
				max_v = left->max_v;
				max_c = left->max_c + right->max_c;
				smax_v = max(left->smax_v,right->smax_v);
			}

			if(left->min_v < right->min_v){
				min_v = left->min_v;
				min_c = left->min_c;
				smin_v = min(left->smin_v,right->min_v);
			} else if(left->min_v > right->min_v){
				min_v = right->min_v;
				min_c = right->min_c;
				smin_v = min(left->min_v,right->smin_v);
			} else{
				min_v = left->min_v;
				min_c = left->min_c + right->min_c;
				smin_v = min(left->smin_v,right->smin_v);
			}
		}
	};

	int n,n0;
	Node *root;

	void _update_min(lint x,int a,int b,Node *nd,int l,int r){
		if(b <= l || r <= a || nd->max_v <= x){
			return;
		}
		if(a <= l && r <= b && nd->smax_v < x){
			nd->update_max(x);
			return;
		}

		nd->push();
		_update_min(x,a,b,nd->left,l,(l+r)/2);
		_update_min(x,a,b,nd->right,(l+r)/2,r);
		nd->update();
	}

	void _update_max(lint x,int a,int b,Node *nd,int l,int r){
		if(b <= l || r <= a || x <= nd->min_v){
			return;
		}
		if(a <= l && r <= b && x < nd->smin_v){
			nd->update_min(x);
			return;
		}

		nd->push();
		_update_max(x,a,b,nd->left,l,(l+r)/2);
		_update_max(x,a,b,nd->right,(l+r)/2,r);
		nd->update();
	}

	void _add_val(lint x,int a,int b,Node *nd,int l,int r){
		if(b <= l || r <= a){
			return;
		}
		if(a <= l && r <= b){
			nd->addalint(x);
			return;
		}

		nd->push();
		_add_val(x,a,b,nd->left,l,(l+r)/2);
		_add_val(x,a,b,nd->right,(l+r)/2,r);
		nd->update();
	}

	void _update_val(lint x,int a,int b,Node *nd,int l,int r){
		if(b <= l || r <= a){
			return;
		}
		if(a <= l && r <= b){
			nd->updatealint(x);
			return;
		}

		nd->push();
		_update_val(x,a,b,nd->left,l,(l+r)/2);
		_update_val(x,a,b,nd->right,(l+r)/2,r);
		nd->update();
	}

	lint _query_max(int a,int b,Node *nd,int l,int r){
		if(b <= l || r <= a){
			return -inf;
		}
		if(a <= l && r <= b){
			return nd->max_v;
		}
		nd->push();
		lint lv = _query_max(a,b,nd->left,l,(l+r)/2);
		lint rv = _query_max(a,b,nd->right,(l+r)/2,r);
		return max(lv,rv);
	}

	lint _query_min(int a,int b,Node *nd,int l,int r){
		if(b <= l || r <= a){
			return inf;
		}
		if(a <= l && r <= b){
			return nd->min_v;
		}
		nd->push();
		lint lv = _query_min(a,b,nd->left,l,(l+r)/2);
		lint rv = _query_min(a,b,nd->right,(l+r)/2,r);
		return min(lv,rv);
	}

	lint _query_sum(int a,int b,Node *nd,int l,int r){
		if(b <= l || r <= a){
			return 0;
		}
		if(a <= l && r <= b){
			return nd->sum;
		}
		nd->push();
		lint lv = _query_sum(a,b,nd->left,l,(l+r)/2);
		lint rv = _query_sum(a,b,nd->right,(l+r)/2,r);
		return lv + rv;
	}

public:
	SegmentTree(int n,lint *a): n(n){
		n0 = 1;
		while(n0 < n) n0 <<= 1;

		Node *nds = new Node[2*n0];
		root = nds;

		nds[0].len = n0;
		for(int i=0; i<n0-1; ++i){
			nds[i].left = &nds[2*i+1];
			nds[i].right = &nds[2*i+2];
			nds[2*i+1].len = nds[2*i+2].len = (nds[i].len >> 1);
		}

		for(int i=0; i<n; ++i) nds[n0-1+i].init(a[i]);
		for(int i=n; i<n0; ++i) nds[n0-1+i].init_empty();
		for(int i=n0-2; i>=0; i--) nds[i].update();
	}

	void update_min(int a,int b,lint x){
		_update_min(x,a,b,root,0,n0);
	}

	void update_max(int a,int b,lint x){
		_update_max(x,a,b,root,0,n0);
	}

	void add_val(int a,int b,lint x){
		_add_val(x,a,b,root,0,n0);
	}

	void update_val(int a,int b,lint x){
		_update_val(x,a,b,root,0,n0);
	}

	lint query_max(int a,int b){
		return _query_max(a,b,root,0,n0);
	}

	lint query_min(int a,int b){
		return _query_min(a,b,root,0,n0);
	}

	lint query_sum(int a,int b){
		return _query_sum(a,b,root,0,n0);
	}
};

lint N;
lint v[100010];

struct con{
	lint l,r,c;
};
bool operator<(const con l,const con r){
	if(l.l==r.l)return l.r<r.r;
	return l.l<r.l;
}

int main(){
	lint n,m;in(n,m);
	vector<con>a(m);
	fill(v,v+100000,linf);v[0]=0;

	SegmentTree t(n,v);
	rep(m){
		cin>>a[i].l>>a[i].r>>a[i].c;--a[i].l;
	}
	sort(all(a));
	rep(m){
		t.update_min(a[i].l+1,a[i].r,min(linf,lint(t.query_sum(a[i].l,a[i].l+1)+a[i].c)));
		//rep(j,n)cout<<t.query_sum(j,j+1)<<" ";cout<<endl;
	}
	lint ans=(t.query_sum(n-1,n));
	if(ans>=linf)o(-1);
	else o(ans);
}


//sub-EOF


Compiler output:
a.cc:166:8: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
  166 | mint<> operator""m(unsigned long long n){ return mint<>(n); }
      |        ^~~~~~~~
a.cc:167:17: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
  167 | mint<998244353> operator""m9(unsigned long long n){ return mint<998244353>(n); }
      |                 ^~~~~~~~
a.cc:168:15: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
  168 | mint<1000003> operator""m3(unsigned long long n){ return mint<1000003>(n); }
      |               ^~~~~~~~
a.cc: In function 'int main()':
a.cc:557:49: error: no matching function for call to 'min(long int, lint)'
  557 |                 t.update_min(a[i].l+1,a[i].r,min(linf,lint(t.query_sum(a[i].l,a[i].l+1)+a[i].c)));
      |                                              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:13:
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:557:49: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'lint' {aka 'long long int'})
  557 |                 t.update_min(a[i].l+1,a[i].r,min(linf,lint(t.query_sum(a[i].l,a[i].l+1)+a[i].c)));
      |                                              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:557:49: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
  557 |                 t.update_min(a[i].l+1,a[i].r,min(linf,lint(t.query_sum(a[i].l,a[i].l+1)+a[i].c)));
      |                                              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~