考虑一个 $dp$ ，设 $dp[R][t]$ 表示在 $t$ 时刻已经解决了 $1 \sim R$ 的所有患者。考虑转移就是枚举下一个治疗计划用哪一个。设下一个治疗计划为 $(l,r,c)$ 那么分为两类：

• $c > t$ ，那么在下一次使用治疗计划的时间在现在之后，由于中间不能有剩余的患者，有 $l \le R-(c-t)$ ，也就是 $c > t,l + c \le R+t$ 。
• $c < t$ ，也就是说之前进行了一次治疗计划用来覆盖 $R$ 后的一段，那么中间没有剩余患者的条件是 $l \le R - (t-c)$ ，也就是 $l - c \le R - t$ 。

在这两种情况下，可以转移到 $dp[r][c]$ 。

当然，也可以画一个图来形象的理解：

其中三个段分别是三个治疗计划，中间的斜线是由于患者在进行感染，后面的人时刻会往前感染。

然后不难发现这两个条件是可以分别计算的，因此只讨论其中第一个条件。不难发现这个 $dp$ 就是一个从点向二维矩形内所有点连边，然后求最短路的问题。可以直接套用弹跳的解法。如果直接这么写了交上去，很可能会获得一个 39 分，后面的点基本都 T 了。

但是事实上，由于是一个前缀，可以把线段树上每个点开 $\text{set}$ 变成线段树上只有叶子开 $\text{set}$ ，因为比较和弹出都只会拿集合中的最小值，所以非叶点就维护一个区间最小值即可，于是就可以 $O(n\log^2 n) \to O(n\log n)$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"

using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int sz;

struct fk {
	int t , T , l , r , c;
} A[MAXN] ;

multiset<pii> S[MAXN << 2][2];

void ins( int rt , int l , int r , int idx ) {
	S[rt][0].insert( mp( A[idx].l + A[idx].T - 1 , idx ) );
	S[rt][1].insert( mp( A[idx].l - A[idx].T - 1 , idx ) );
	if( l == r ) return;
	int m = l + r >> 1;
	if( A[idx].t <= m ) ins( rt << 1 , l , m , idx );
	else ins( rt << 1 | 1 , m + 1 , r , idx );
}

priority_queue<pair<ll,int>> Q;
ll dis[MAXN];
int vis[MAXN];

ll ds;

void era( int rt , int w , pair<int,int> p ) {
	while( rt ) {
		S[rt][w].erase( S[rt][w].find( p ) );
		rt >>= 1;
	}
}
int w , lim , L , R;
void fuck( int rt , int l , int r ) {
	if( S[rt][w].empty() ) return;
	int i = S[rt][w].begin() -> se;
	if( lim < ( w ? A[i].l - A[i].T - 1 : A[i].l + A[i].T - 1 ) ) return;
	if( l == r ) {
		while( lim >= ( w ? A[i].l - A[i].T - 1 : A[i].l + A[i].T - 1 ) ) {
			if( !vis[i] && dis[i] > ds ) {
				dis[i] = ds;
				vis[i] = 1;
				Q.push( mp( -( ds + A[i].c ) , i ) );
			}
			era( rt , w , *S[rt][w].begin() );
			if( S[rt][w].empty() ) return;
			i = S[rt][w].begin() -> se;
		}
		return;
	}
	int m = l + r >> 1;
	if( L <= m ) fuck( rt << 1 , l , m );
	if( R > m ) fuck( rt << 1 | 1 , m + 1 , r );
}

void solve() {
	cin >> n >> m;
	vi ts;
	rep( i , 1 , m ) {
		int t , l , r , c;
		scanf("%d%d%d%d",&t,&l,&r,&c);
		A[i] = (fk) { 0 , t , l , r , c };
		ts.pb( t );
	}
	sort( all( ts ) );
	ts.erase( unique( all( ts ) ) , ts.end() );
	rep( i , 1 , m ) A[i].t = lower_bound( all( ts ) , A[i].T ) - ts.begin() + 1;
	sz = ts.size();
	rep( i , 1 , m ) if( A[i].l != 1 ) ins( 1 , 1 , sz , i );
//	cout << "OK" << endl;
	memset( dis , 0x3f , sizeof dis );
	rep( i , 1 , m ) 
		if( A[i].l == 1 ) dis[i] = 0 , Q.push( mp( -A[i].c , i ) );
	while( !Q.empty() ) {
		auto t = Q.top().se; ds = -Q.top().fi; Q.pop();
		
		w = 0 , lim = A[t].r + A[t].T , L = A[t].t , R = sz;
		fuck( 1 , 1 , sz );
		w = 1 , lim = A[t].r - A[t].T , L = 1 , R = A[t].t - 1 ;
		if( A[t].t ) fuck( 1 , 1 , sz );
	}
	ll as = 0x3f3f3f3f3f3f3f3f;
	rep( i , 1 , m ) if( A[i].r == n ) as = min( as , dis[i] + A[i].c );
	cout << ( as > 1e18 ? -1 : as ) << endl;
}

signed main() {
//	freopen("04-22.in","r",stdin);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}