// 01001100 01001111 01010100 01000001 \\
// \\
// ╦ ╔═╗╔╦╗╔═╗ \\
// ║ ║ ║ ║ ╠═╣ \\
// ╩═╝╚═╝ ╩ ╩ ╩ \\
// \\
// 01001100 01001111 01010100 01000001 \\
#include <bits/stdc++.h>
using namespace std;
#define N 200002
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int n, m, x;
vector<pii> q;
int mx[N];
int cnt[N];
vector<int> mr[N];
void built(){
for(int i = 0; i < n; i++){
mr[i] = {0};
mx[i] = cnt[i] = 0;
}
}
void add(int l, int r, int val){
for(int i = l; i < r; i++)
mx[i] += val;
}
pii get(){
pii pi = {0, 0};
for(int i = 1; i < n && mx[i] <= x; i++)
if(mr[i].back() > pi.ss) pi = {i, mr[i].back()};
return pi;
}
int get_mx(int l, int r){
int ans = 0;
for(int i = l; i < r; i++)
ans = max(ans, mx[i]);
return ans;
}
void Insert(int l, int r){
mr[l].append(r);
}
void remove(int l){
mr[l].pop_back();
}
bool check(int c){
x = c;
pii pi;
built();
for(auto & [i, j] : q){
cnt[i]++;
if(cnt[i] > x){
add(0, i, 1);
add(j, n, 1);
}
else{
add(i, j, 1);
Insert(i, j);
}
while(get_mx(0, n) > x){
pi = get();
if(!pi.ff) return 0;
remove(pi.ff);
add(0, pi.ff, 1);
add(pi.ss, n, 1);
add(pi.ff, pi.ss, -1);
}
}
return 1;
}
void solve(){
int l, r, c;
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> l >> r >> c;
if(l > r) swap(l, r);
for(int j = 0; j < c; j++)
q.append({l, r});
}
int ans = 0;
sort(all(q));
for(int i = 65536; i > 0; i /= 2)
if(!check(ans + i)) ans += i;
cout << ans + 1;
}
int terminator(){
L0TA;
solve();
return 0;
}
