#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;

//common
typedef int  i32;
typedef long long i64,ll;
#define BR "\n"

#define ALL(c) (c).begin(),(c).end()
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;

//config
#define MODE_DEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;

//debug
#ifdef NDEBUG
#define DUMP(x)
#define DUMPLN(x)
#define DEBUG(x)
#define DEBUGLN(x)
#define LINE()
#define LINELN()
#define CHECK(exp,act)
#define STOP(e)
#else
#define DUMP(x)  cerr << #x << " = " << (x)
#define DUMPLN(x)  DUMP(x) <<endl
#define DEBUG(x) DUMP(x) << LINE() << " " << __FILE__
#define DEBUGLN(x) DEBUG(x)<<endl
#define LINE()    cerr<< " (L" << __LINE__ << ")"
#define LINELN()    LINE()<<endl
#define CHECK(exp,act)  if(exp!=act){DUMPLN(exp);DEBUGLN(act);}
#define STOP(e)  CHECK(e,true);if(!(e)) exit(1);
#endif

template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
	}
	return ss.str();
}
template<class T> inline string toString(const vector<vector<T> >& map) {
	stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)ss<< p.first<<":" << p.second<<" ";
	return ss.str();
}

template<typename T,typename V> inline T mod(T v,V MOD){
	return (v%MOD+MOD)%MOD;
}

#define nextInt(n) scanf("%d",&n)
#define nextLong(n) scanf("%lld",&n)
#define nextDouble(n) scanf("%lf",&n)

namespace ShortestPath{

    typedef ll Cost;
    const Cost CINF=1LL<<58;
    typedef  vector<vector<Cost> > Mat;
    struct Edge{
        int from,to;Cost cost;
        Edge(int from,int to,Cost cost)
            : from(from),to(to),cost(cost) {};
    };
    ostream& operator <<(ostream& os,const Edge& e){
            os<<"("<<e.from<<"->"<<e.to<<")";
            return os;
    }
    typedef vector<vector<Edge> > Graph;

    struct Task{
        int prev,pos,cost;
        Task(int prev,int pos,int cost)
            :prev(prev),pos(pos),cost(cost){};
        bool operator>(const Task& r) const{
            return cost>r.cost;
        }
    };

    vector<Cost> dijkstra(const Graph& g,const int s,vector<int>& prev){
        const int V=g.size();
        vector<Cost> d(V,CINF);d[s]=0;
        fill(ALL(prev), -2);
        priority_queue<Task,vector<Task>,greater<Task> > que;
        que.push(Task(-1,s,0));
        while(!que.empty()){
            Task task=que.top();que.pop();
            if(d[task.pos]<task.cost)continue;
            EACH(e,g[task.pos]){
                if(d[e->to]>d[e->from]+e->cost){
                    d[e->to]=d[e->from]+e->cost;
                    que.push(Task(e->from,e->to,d[e->to]));
                }
            }   
        }
        return d;
    }
    vector<Cost> dijkstra(const Graph& g,const int s){
        vector<int> prev(g.size());return dijkstra(g,s,prev);
    }

}
using namespace ShortestPath;



ll INF=1LL<<58;
class Main{
public:	
	void run(){
		int L,n;cin >> L >>n;
		map<int,int> xs;int ind=0;
		xs[0]=ind++;xs[L]=ind++;
		int i=0;
		vector<pair<int,pair<int,int> > > dts(n);
		REP(i,n){
			int p,d,t;cin >> p >> d >> t;
			if(xs.count(p)==0)xs[p]=ind++;
			if(xs.count(p+d)==0)xs[p+d]=ind++;
			dts[i]=make_pair(p,make_pair(p+d,t));
		}
		Graph g(xs.size());
		EACH(it,xs)EACH(it2,xs)if(it2->first>it->first){
			g[it->second].push_back(Edge(it->second,it2->second,(ll)it2->first-it->first));
		}
		REP(i,n){
			g[xs[dts[i].first]].push_back(Edge(xs[dts[i].first],xs[dts[i].second.first],dts[i].second.second));
		}

		cout << dijkstra(g,0)[1] <<endl;
	}
};
 int main(){
 	cout <<fixed<<setprecision(15);
	ios::sync_with_stdio(false);
 	Main().run();
 	return 0;
 }


Measured memory_bytes: 49120