/* in the name of god */ //#pragma GCC optimize("Ofast,O3,unroll-loops") //#pragma GCC target("avx,avx2,fma") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native") #include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll ; #define File freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define all(V) V.begin(),V.end() #define setprec(x) fixed << setprecision(x) #define Mp(a,b) make_pair(a,b) #define len(V) (int)(V.size()) #define sep ' ' #define endl '\n' #define pb push_back #define fi first #define sec second #define popcount(x) __builtin_popcount(x) #define lid u<<1 #define rid (lid)|1 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 20 + 10,SQ=320,LOG=31; const ll inf = 2e9 , MD = 1e9 + 7; inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);} int n , m ; int a[N],b[N],c[N]; int ps[N]; int32_t main() { ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0); cin >> n >> m ; for(int i=0 ;i < m;i++){ cin >> a[i] >> b[i] >> c[i]; if(a[i] > b[i]) swap(a[i],b[i]); } int ans = inf; for(int mask = 0 ;mask < (1<<m);mask++){ fill(ps,ps+n+2,0); for(int j = 0; j < m;j++){ if(mask&(1<<j)){ ps[a[j]]++; ps[b[j]]--; } else{ ps[b[j]]++; ps[n+1]--; ps[1]++; ps[a[j]]--; } } for(int j = 1;j <= n;j++) ps[j] += ps[j-1]; int mx = 0; for(int j =1 ;j <= n;j++) mx = max(mx,ps[j]); ans = min(ans,mx); } cout << ans << endl; return 0; }