#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=a; i>=b; i--)
#define pb push_back
#define fi first
#define se second
int main(){
ios::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
int n,m; cin>>n>>m;
vi a(m), b(m), c(m); FOR(i,0,m) cin>>a[i]>>b[i]>>c[i];
FOR(i,0,m){
if (a[i]>b[i]) swap(a[i],b[i]);
}
vector<ll> cnt;
ll mn = m;
FOR(i,0,(1<<m)){
cnt.assign(n+1,0);
FOR(j,0,m){
if (i&(1<<j)){
cnt[a[j]+1]++; if (b[j]<n) cnt[b[j]+1]--;
}else{
cnt[1]++; cnt[a[j]+1]--; if (b[j]<n) cnt[b[j]+1]++;
}
}
FOR(j,1,n+1) cnt[j] += cnt[j-1];
ll mx = 0; FOR(j,1,n+1) mx = max(mx, cnt[j]);
//cout<<" "; FOR(j,1,n+1) cout<<cnt[j]<<" ";
//cout<<"\n";
FOR(j,1,n+1) mn=min(mn,mx);
}
cout<<mn<<"\n";
return 0;
}
