//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second #define endl '\n' int n,m; int aa[200001]; int bb[200001]; int cc[200001]; int co[200001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m; for(int i=0;i<m;i++){ cin>>aa[i]>>bb[i]>>cc[i]; aa[i]--; bb[i]--; } int ans=m; for(int i=0;i<(1<<m);i++){ for(int j=0;j<n;j++){ co[j]=0; } for(int j=0;j<m;j++){ if(i&(1<<j)){ int cur=aa[j]; while(cur!=bb[j]){ co[cur]++; cur=(cur+1)%n; } } else{ int cur=bb[j]; while(cur!=aa[j]){ co[cur]++; cur=(cur+1)%n; } } } int ma=0; for(int j=0;j<n;j++){ ma=max(ma,co[j]); } ans=min(ans,ma); } cout<<ans<<endl; return 0; }