#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3;
long long int a[maxn + 100], b[maxn + 100];
vector <pair <pair <int, int>, int>> s;
int n;
bool check(int x)
{
long long int p = 0;
int ptr = 0;
multiset <int> av;
for (int i = 1;i < n;i++)
{
b[i] = 0;
}
for (int i = 1;i < n;i++)
{
b[i] += b[i - 1];
while (ptr < s.size() and s[ptr].first.first == i)
{
av.insert(s[ptr++].first.second);
}
while (av.size() and (*(av.begin())) <= i)
{
av.erase(av.begin());
}
int cur = a[i] + p + b[i];
int tmp = ((x - p) - cur + 1) / 2;
for (int i = 0;i < tmp;i++)
{
if (av.size())
{
int r = *(--av.end());
av.erase(--av.end());
p++;
b[r] -= 2;
}
else
{
return 0;
}
}
}
return p == x;
}
bool solve(int k)
{
for (int i = 1;i < n;i++)
{
a[i] += k;
}
bool ret = 0;
for (int i = 0;i <= k;i++)
{
ret |= check(i);
}
for (int i = 1;i < n;i++)
{
a[i] -= k;
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int m;
cin >> n >> m;
if (m > maxn)
{
return 0;
}
for (int i = 1;i <= m;i++)
{
int l, r, c;
cin >> l >> r >> c;
if (l > r)
{
swap(l, r);
}
s.push_back({{l, r}, c});
a[l] -= c;
a[r] += c;
}
for (int i = 1;i < n;i++)
{
a[i] += a[i - 1];
}
sort(s.begin(), s.end());
int l = 0, r = m;
while (r - l != 1)
{
int mid = (l + r) / 2;
if (solve(mid))
{
r = mid;
}
else
{
l = mid;
}
}
cout << r;
}
