#include <bits/stdc++.h> using namespace std; vector<pair<pair<long long, long long>, long long>> wyma; long long roz[200007]; long long ile[200007]; long long sumakon[200007]; long long maxseg = -1, gdziemax, n, m; vector<pair<long long, long long>> przechodzace[200007]; long long cof[200007]; long long gdziemax2; bool spr(long long sr, long long ilezw) { if(ilezw < 0) { return false; } priority_queue<pair<long long, long long>> pq; for(long long i = 0; i < n + 3; i++) { sumakon[i] = 0; } long long cur = 0; long long zostalo = ilezw; for(long long i = 1; i <= gdziemax; i++) { for(auto x : przechodzace[i]) { pq.push(x); } while(ile[i] - cur + zostalo > sr) { if(pq.empty()) { return false; } auto x = pq.top(); pq.pop(); long long potrzeb = ile[i] - cur + zostalo - sr; long long minn = min(x.second, (potrzeb + 1) / 2); cur += minn; zostalo -= minn; sumakon[x.first + 1] += 2 * minn; x.second -= minn; if(x.second > 0) { pq.push(x); } } } sumakon[gdziemax + 1] -= cur; for(long long i = gdziemax + 1; i <= n; i++) { sumakon[i] += sumakon[i - 1]; if(ile[i] + sumakon[i] > sr) { return false; } } return true; } long long policz(long long gdzie) { gdziemax = gdzie; for(long long i = 0; i < n + 3; i++) { przechodzace[i].clear(); } for(auto x : wyma) { if(x.first.first <= gdziemax && gdziemax <= x.first.second) { przechodzace[x.first.first].push_back({x.first.second, x.second}); } } long long l = 0, r = maxseg; while(l < r) { long long sr = (l + r) / 2; if(spr(sr, maxseg - sr) || spr(sr, maxseg - sr + 1)) { r = sr; } else { l = sr + 1; } } return l; } int main() { cin >> n >> m; for(long long i = 0; i < m; i++) { long long a, b, c; cin >> a >> b >> c; if(a > b) { swap(a, b); } wyma.push_back({{a, b - 1}, c}); roz[a] += c; roz[b] -= c; } for(long long i = 1; i <= n; i++) { ile[i] = ile[i - 1] + roz[i]; if(maxseg < ile[i]) { maxseg = ile[i]; gdziemax = i; } if(maxseg == ile[i]) { gdziemax2 = i; } } cout << min(policz(gdziemax), policz(gdziemax2)) << endl; return 0; }