#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
int main() {
ll n, m; cin >> n >> m;
vector<ll> a(m), b(m), c(m);
for(ll i=0; i<m; i++){
cin >> a[i] >> b[i] >> c[i];
a[i]--;
b[i]--;
if(a[i]>b[i]) swap(a[i], b[i]);
}
ll ans;
for(ll i=0; i<(1<<m); i++){
vector<ll> s(n, 0);
ll cnt=0;
for(ll j=0; j<m; j++){
if(i&(1<<j)){
s[a[j]]++;
s[b[j]]--;
} else {
s[0]++;
s[a[j]]--;
s[b[j]]++;
}
}
ll curr=0;
for(ll j=0; j<n; j++){
curr+=s[j];
cnt=max(curr, cnt);
}
if(i==0) ans=cnt;
else ans=min(ans, cnt);
}
cout << ans << endl;
}
