// https://www.luogu.com.cn/article/lqa8q1lu
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 2e5 + 5;
int n, m, p;
long long a[N], delta[N];
vector<array<int, 2>> g[N];
bool solve(long long cnt, long long k) {
fill(delta + 1, delta + n + 1, 0);
priority_queue<array<int, 2>> pq;
long long cur = 0;
for (int i = 1; i <= p; ++i) {
for (auto [j, c] : g[i]) {
if (j > p) {
pq.push({j, c});
}
}
long long need = (a[i] + cnt - k + 1) / 2;
while (cur < need) {
if (!pq.size()) {
return 0;
}
auto [j, c] = pq.top(); pq.pop();
long long x = need - cur;
if (c > x) {
c -= x;
cur = need;
delta[j] += x;
pq.push({j, c});
} else {
delta[j] += c;
cur += c;
}
}
}
for (int i = p + 1; i <= n; ++i) {
cur -= delta[i];
if (a[i] + cnt - 2 * cur > k) {
return 0;
}
}
return 1;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
while (m--) {
int l, r, c; cin >> l >> r >> c;
if (l > r) {
swap(l, r);
}
a[l] += c;
a[r] -= c;
g[l].push_back({r, c});
}
for (int i = 1; i <= n; ++i) {
a[i] += a[i - 1];
}
p = max_element(a + 1, a + n + 1) - a;
auto check = [&](long long k) -> bool {
for (auto it : {0, 1}) {
if (solve(a[p] - k + it, k)) {
return 1;
}
}
return 0;
};
long long l = 1, r = a[p], res = a[p];
while (l <= r) {
long long md = (l + r) / 2;
if (check(md)) {
res = md;
r = md - 1;
} else {
l = md + 1;
}
}
cout << res;
return 0;
}
