#include <bits/stdc++.h> using namespace std; const int maxn = 2e5; long long int a[maxn + 100], b[maxn + 100]; vector <pair <pair <int, int>, int>> s; int n, ans; 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; } } } if (p == x) { ans = x; } return p > x; } bool solve(int k) { for (int i = 1;i < n;i++) { a[i] += k; } ans = 0; int l = -1, r = k + 1; while (r - l > 1) { int mid = (l + r) / 2; if (check(mid)) { l++; } else { r = mid; } } check(l); for (int i = 1;i < n;i++) { a[i] -= k; } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int m; cin >> n >> m; 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; }