// 01001100 01001111 01010100 01000001 \\
// \\
// ╦ ╔═╗╔╦╗╔═╗ \\
// ║ ║ ║ ║ ╠═╣ \\
// ╩═╝╚═╝ ╩ ╩ ╩ \\
// \\
// 01001100 01001111 01010100 01000001 \\
#include <bits/stdc++.h>
using namespace std;
#define N 100001
#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[4 * N];
int lazy[4 * N];
vector<pii> mr[4 *N];
void built(int v = 1, int s = 0, int e = n){
mr[v] = {{0, 0}};
mx[v] = lazy[v] = 0;
if(e - s == 1) return;
int lc, rc, mid;
lc = 2 * v;
rc = 2 * v + 1;
mid = (s + e) / 2;
built(lc, s, mid);
built(rc, mid, e);
}
void push(int v){
int lc, rc;
lc = 2 * v;
rc = lc + 1;
mx[v] += lazy[v];
lazy[lc] += lazy[v];
lazy[rc] += lazy[v];
lazy[v] = 0;
}
void add(int l, int r, int val, int v = 1, int s = 0, int e = n){
push(v);
if(r <= s || e <= l || r <= l) return;
if(l <= s && e <= r){
lazy[v] += val;
push(v);
return;
}
int lc, rc, mid;
push(v);
lc = 2 * v;
rc = 2 * v + 1;
mid = (s + e) / 2;
add(l, r, val, lc, s, mid);
add(l, r, val, rc, mid, e);
mx[v] = max(mx[lc], mx[rc]);
}
pii get(int v = 1, int s = 0, int e = n){
push(v);
if(mx[v] <= x) return mr[v].back();
if(e - s == 1) return {0, 0};
pii pi, pj;
int lc, rc, mid;
lc = 2 * v;
rc = 2 * v + 1;
mid = (s + e) / 2;
pi = pj = get(lc, s, mid);
if(mx[lc] <= x)
pj = get(rc, mid, e);
if(pj.ss > pi.ss)
swap(pi, pj);
return pi;
}
int get_mx(int l, int r, int v = 1, int s = 0, int e = n){
if(r <= s || e <= l || r <= l) return 0;
if(l <= s && e <= r) return mx[v];
int lc, rc, mid;
push(v);
lc = 2 * v;
rc = 2 * v + 1;
mid = (s + e) / 2;
return max(get_mx(l, r, lc, s, mid), get_mx(l, r, rc, mid, e));
}
void Insert(int l, int r, int v = 1, int s = 0, int e = n){
if(e - s == 1){
mr[v].append({l, r});
return;
}
int lc, rc, mid;
push(v);
lc = 2 * v;
rc = 2 * v + 1;
mid = (s + e) / 2;
if(l < mid) Insert(l, r, lc, s, mid);
else Insert(l, r, rc, mid, e);
mr[v].clear();
if(mr[rc].back().ss > mr[lc].back().ss)
mr[v].append(mr[rc].back());
else mr[v].append(mr[lc].back());
}
void remove(int l, int v = 1, int s = 0, int e = n){
if(e - s == 1){
mr[v].pop_back();
return;
}
int lc, rc, mid;
push(v);
lc = 2 * v;
rc = 2 * v + 1;
mid = (s + e) / 2;
if(l < mid) remove(l, lc, s, mid);
else remove(l, rc, mid, e);
mr[v].clear();
if(mr[rc].back().ss > mr[lc].back().ss)
mr[v].append(mr[rc].back());
else mr[v].append(mr[lc].back());
}
bool check(int c){
x = c;
pii pi;
built();
for(auto & [i, j] : q){
add(i + 1, j + 1, 1);
Insert(i, j);
while(mx[1] > x){
pi = get();
if(!pi.ff) return 0;
remove(pi.ff);
add(0, pi.ff + 1, 1);
add(pi.ss + 1, n, 1);
add(pi.ff + 1, pi.ss + 1, -1);
}
}
return 1;
}
void solve(){
int l, r, c;
cin >> n >> m;
n++;
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});
}
sort(all(q));
int ans = 0;
for(int i = 65536; i > 0; i /= 2)
if(!check(ans + i)) ans += i;
cout << ans + 1;
}
int terminator(){
L0TA;
solve();
return 0;
}
