#include <bits/stdc++.h>
using namespace std;
int seg[1 << 19];
int lazy[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
void build(int c, int l, int r){
lb[c] = l;
rb[c] = r;
seg[c] = 0;
lazy[c] = 0;
if(l == r) return;
int k = (l+r)/2;
build(2*c, l, k);
build(2*c+1, k+1, r);
}
inline void prop(int c){
seg[c] += lazy[c];
if(lb[c] != rb[c]){
lazy[2*c] += lazy[c];
lazy[2*c+1] += lazy[c];
}
lazy[c] = 0;
}
void update(int c, int l, int r, int x = 1){
if(lb[c] == l && rb[c] == r) lazy[c] += x;
prop(c);
if(lb[c] == l && rb[c] == r) return;
int k = (lb[c] + rb[c])/2;
if(l <= k && k < r){
update(2*c, l, k, x);
update(2*c+1, k+1, r, x);
}else if(r <= k){
update(2*c, l, r, x);
prop(2*c+1);
}else{
prop(2*c);
update(2*c+1, l, r, x);
}
seg[c] = max(seg[2*c], seg[2*c+1]);
}
int query(int c, int l, int r){
prop(c);
if(lb[c] == l && rb[c] == r) return seg[c];
int k = (lb[c] + rb[c])/2;
if(l <= k && k < r) return max(query(2*c, l, k), query(2*c+1, k+1, r));
else if(r <= k) return query(2*c, l, r);
else return query(2*c+1, l, r);
}
int main(){
int n, m;
scanf("%d%d",&n,&m);
vector<tuple<int,int,int> > dat;
for(int i = 0; i < m; i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a > b) swap(a, b);
b--;
dat.emplace_back(a,b,c);
}
sort(dat.begin(), dat.end(), [](tuple<int,int,int> x, tuple<int,int,int> y){
return get<1>(x) < get<1>(y);
});
int ans = 1e9;
for(int bit = 0; bit < (1 << m); bit++){
build(1, 1, n);
for(int i = 0; i < m; i++){
int l, r, c;
tie(l, r, c) = dat[i];
if(bit & (1 << i)){
update(1, 1, n, 1);
update(1, l, r, -1);
}else{
update(1, l, r, 1);
}
}
ans = min(ans, query(1, 1, n));
}
printf("%d\n", ans);
return 0;
}
