#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 (s[ptr].first.first == i) { av.insert(s[ptr++].first.second); } int cur = a[i] + p + b[i]; for (int i = 0;i < ((x - p) - cur + 1) / 2;i++) { if (av.size()) { int r = *(--av.end()); av.erase(--av.end()); p++; b[r]--; } 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() { 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; }