#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;

typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
#define fr first
#define sc second
#define INF ( 1 << 30 )

int L, n;
Pii data[1000];
map< int , int > used;

int dis( int a, int b){
  return b - a;
}


int rec( int point, int pos){
  if(used.find(point) != used.end()) return used[point];

  if(pos == n){
    return dis( point, L);
  }
  if( point == data[pos].fr ){
    int ret = dis( point, L);
    if(pos + 1 < n) ret = min( rec( data[pos + 1].fr, pos + 1) + dis( data[pos].fr, data[pos + 1].fr), ret);
    ret = min( ret, rec( point + data[pos].sc.fr, pos + 1) + data[pos].sc.sc);
    return used[point] = ret;
  }else if(point > data[pos].fr){
    return rec( point , pos + 1);
  }else{
    return rec( data[pos].fr, pos) + dis( point, data[pos].fr);
  }
}


int main(){
  cin >> L >> n;
  for(int i = 0 ; i < n ; i++ ){
    cin >> data[i].fr >> data[i].sc.fr >> data[i].sc.sc;
  }
  sort( data, data + n);

  cout << rec( 0, 0) << endl;
}
