#include<bits/stdc++.h>
using namespace std;
int maxA, N, M, b[3009], a[3009], l[3009], r[3009], c[3009], aib[3009];
vector < int > v[3009];
void U (int pos, int val)
{
while (pos <= N)
aib[pos] += val,
pos += pos - (pos & (pos - 1));
}
int Q (int pos)
{
int sum = 0;
while (pos)
sum += aib[pos],
pos &= pos - 1;
return sum;
}
int getSign (int S, int cntFlipped)
{
if (cntFlipped > M) return 0;
for (int i=1; i<=N; i++)
{
int newA = a[i] + cntFlipped;
if (newA < S) b[i] = 0;
else b[i] = (newA + 1 - S) / 2;
}
for (int i=1; i<=N; i++)
aib[i] = 0;
bool ok = 1;
int used = 0;
priority_queue < int > PQ;
for (int i=1; i<=N; i++)
{
for (auto r : v[i])
PQ.push (r);
int needed = max (0, b[i] - Q (N - i + 1));
if (needed > PQ.size ()) return 0;
while (needed --)
{
int r = PQ.top ();
PQ.pop (), used ++;
U (N - r + 1, +1);
}
}
return (used <= cntFlipped);
}
bool ok (int S)
{
if (S >= maxA) return 1;
if (getSign (S, maxA - S)) return 1;
if (getSign (S, maxA - S + 1)) return 1;
return 0;
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d %d", &N, &M);
///N links: 1-2, 2-3, .., N-1
for (int i=1; i<=M; i++)
{
scanf ("%d %d %d", &l[i], &r[i], &c[i]);
if (l[i] > r[i]) swap (l[i], r[i]);
a[l[i]] ++, a[r[i]] --;
v[l[i]].push_back (r[i] - 1);
}
int p = 1, u = 0, mij, ras;
for (int i=1; i<=N; i++)
a[i] += a[i - 1], u = max (u, a[i]);
maxA = u;
while (p <= u)
{
mij = (p + u) >> 1;
if (ok (mij)) ras = mij, u = mij - 1;
else p = mij + 1;
}
printf ("%d\n", ras);
return 0;
}
