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