/* WHY NOT ? */
// #pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define endl '\n'
#define mn first
#define mnc second
#define int long long
int MAX = 1e5;
int MAXN = 2 * MAX + 2;
vector<pair<int,int>> tree;
vector<int> lazy;
// pair<int,int> tree[4 * MAXN];
// int lazy[4 * MAXN];
pair<long long, long long> merge(pair<long long, long long> a,
pair<long long, long long> b) {
if (a.first < b.first) { return a; }
if (a.first > b.first) { return b; }
return {a.first, a.second + b.second};
}
void push(int node,int ss,int se){
if(lazy[node] != 0){
tree[node].mn += lazy[node];
if(ss != se){
lazy[2 *node] += lazy[node];
lazy[2 *node + 1] += lazy[node];
}
lazy[node] = 0;
}
}
void build(int node,int ss,int se){
if(ss == se){
tree[node].mn = 0;
tree[node].mnc = 1;
lazy[node] = 0;
return;
}
int mid = (ss + se) / 2;
build(2 * node,ss,mid);
build(2 * node + 1,mid + 1,se);
tree[node] = merge(tree[2*node],tree[2*node+1]);
}
void update(int l,int r,int v,int node,int ss = 0,int se = MAXN - 1){
if(l > r) return;
if(ss > r || se < l)return ;
push(node,ss,se);
if(ss >= l && se <= r){
tree[node].mn += v;
if(ss != se){
lazy[2 * node] += v;
lazy[2 * node + 1] += v;
}
return ;
}
int mid = (ss + se) / 2;
update(l,r,v,2 * node,ss,mid);
update(l,r,v,2 * node + 1,mid + 1,se);
push(2 * node,ss,mid);
push(2 * node + 1,mid + 1,se);
tree[node] = merge(tree[2*node],tree[2*node + 1]);
}
pair<int,int> query(int node,int ss,int se,int l,int r){
if(ss > r || se < l){
pair<int,int> ret;
ret.first = 1e9;
ret.second = 1;
return ret;
}
push(node,ss,se);
if(ss >= l && se <= r){
return tree[node];
}
int mid = (ss + se) / 2;
pair<int,int> lft = query(2 * node,ss,mid,l,r);
pair<int,int> rgt = query(2 * node + 1,mid + 1,se,l,r);
push(2 * node,ss,mid);
push(2 * node + 1,mid + 1,se);
pair<int,int> ans = merge(lft,rgt);
return ans;
}
/* more_precisely [ total elements - #(min_elements)] */
/* return number of non - zero elements */
int query(){
return MAXN - query(1,0,MAXN-1,0,MAXN-1).mnc;
}
/* build(1,0,MAXN-1); */
void solve(){
/* https://www.youtube.com/watch?v=iMjd2QI6NEs*/
/* refer for solution */
int n,m;
cin>>n>>m;
MAXN = n + 1;
tree = vector<pair<int,int>> (4 * MAXN);
lazy = vector<int> (4 * MAXN,0);
build(1,0,MAXN - 1);
vector<pair<int,int>> p(m);
vector<int> c(m,0);
for(int i=0;i<m;i++){
cin>>p[i].first>>p[i].second;
cin>>c[i];
p[i].first--;
p[i].second--;
update(p[i].first,p[i].second-1,1,1);
}
vector<vector<int>> start(n + 1),end(n + 1);
for(int i=0;i<m;i++){
start[p[i].first].push_back(i);
end[p[i].second].push_back(i);
}
int ans = query();
for(int i=0;i<n;i++){
for(auto j : start[i]){
update(p[j].first,p[j].second-1,-1,1);
update(0,p[j].first - 1,1,1);
update(p[j].second,n-1,1,1);
}
for(auto j:end[i]){
update(p[j].first,p[j].second-1,1,1);
update(0,p[j].first-1,-1,1);
update(p[j].second,n-1,-1,1);
}
ans = min(ans,query());
}
cout<<ans<<endl;
}
signed main(){
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--){
solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-6 << " miliseconds.\n";
return 0;
}
