/* 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 = 3e3 + 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 ; vector<int> L[N]; multiset<int> s1,s2; inline bool can(int f,int k){ s1.clear(); s2.clear(); int num = 0; for(int i = 1;i <= n;i++){ for(auto h : L[i]) s1.insert(h); if((*s1.begin()) == i) s1.erase(*s1.begin()); if((*s2.begin()) == i) s2.erase(*s2.begin()); while(f - len(s2) + len(s1) > k){ int x = *s1.rbegin(); s1.erase(s1.find(x)); s2.insert(x); num++; if(num > f) return 0; } } return 1; } bool check(int k){ for(int f = 0 ;f <= k;f++){ if(can(f,k)) return 1; } return 0; } int32_t main() { ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0); cin >> n >> m ; for(int i = 1;i <= m;i++){ int a,b,c; cin >> a >> b >> c ; if(a > b) swap(a,b); L[a].pb(b); } int l = 0,r= m; while(r-l>1){ int mid = (l+r)>>1; if(check(mid)) r = mid; else l = mid; } cout << r << endl; return 0; }