/*
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;
}
