#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
pair<int, int> ranges[m];
bool used[m];
for(int i = 0; i<m; i++){
used[i] = false;
int a, b;
cin >> a >> b;
a--;
b--;
int c;
cin >> c;
if(a>b){
swap(a,b);
}
a++;
ranges[i] = make_pair(a,b);
// cout << "! " << a << " " << b << endl;
}
int ans = m;
for(int i = 0; i<(1<<m); i++){
int ar[n];
for(int i = 0; i<=n; i++){
ar[i] = 0;
}
int now = 0;
for(int j = 0; j<m; j++){
bool on = (i&(1<<j))!=0;
if(on){
for(int k = ranges[j].first; k<=ranges[j].second; k++){
ar[k]++;
now = max(now,ar[k]);
}
}
else{
for(int k = 0; k<ranges[j].first; k++){
ar[k]++;
now = max(now,ar[k]);
}
for(int k = ranges[j].second+1; k<n; k++){
ar[k]++;
now = max(now, ar[k]);
}
}
}
ans = min(ans,now);
}
// while(true){
// bool did = false;
// for(int i = 0; i<m; i++){
// int outmax = 0;
// int inmax = 0;
// // cout << "A " << i << endl;
// // cout << "B " << i << endl;
// for(int j = 0; j<n; j++){
// if(j>=ranges[i].first && j<=ranges[i].second){
// inmax = max(inmax,ar[j]);
// }
// else{
// outmax = max(outmax,ar[j]);
// }
// }
// // cout << "X " << i << " " << inmax << " " << outmax << endl;
// if(used[i]==false){
// if(inmax-1 <= outmax){
// continue;
// }
// // cout << "DOING " << i << endl;
// did = true;
// for(int j = 0; j<n; j++){
// if(j>=ranges[i].first && j<=ranges[i].second){
// ar[j]--;
// }
// else{
// ar[j]++;
// }
// }
// }
// else{
// if(outmax-1 <= inmax){
// continue;
// }
// did = true;
// for(int j = 0; j<n; j++){
// if(j>=ranges[i].first && j<=ranges[i].second){
// ar[j]++;
// }
// else{
// ar[j]--;
// }
// }
// }
// used[i] = !used[i];
// }
// if(!did){
// break;
// }
// }
// int ans = 0;
// for(int i = 0; i<n; i++){
// ans = max(ar[i],ans);
// }
cout << ans << endl;
}
