#include <bits/stdc++.h>
using namespace std;
// Solution:
// We can binary search the answer. We also break the circle to
// a line segment.
//
// If intervals [a, b] and [c, d] is reversed, and a < b < c < d,
// then we originally have interval values:
// ([1, a), 0), ([a, b], 1), ((b, c), 0), ([c, d], 1), ((d, N], 0)
// and reversed values are:
// ([1, a), 2), ([a, b], 1), ((b, c), 2), ([c, d], 1), ((d, N], 2)
// We can see that all regions increased - thus all flipped intervals
// must share a point t.
//
// For a fixed point t, let a[i] be the sum of people travelling through i,
// and b[i] be the final one once we reversed optimally. Then b[t] = max(b[i])
// or b[t] = max(b[i]) - 1. This allows us to check only a[t] - max_ans and
// a[t] - max_ans + 1 flips for a point t, where max_ans is the current
// mid in the binary search. Proof follows.
//
// Assume then b[t] < max(b[i]) - 1. Then we can find two reversed segments [a, b] and
// [c, d], such that a is the minimum coordinate of reversed segment and d is the
// maximum one of reversed segments. By definition, [a, b] and [c, d] passes through t,
// and we can unreverse them. This will not change max(b[i]), and increment b[t] by either
// 1 or 2. Thus we can keep doing this until the condition is satisfied without breaking
// the solution.
//
// This yields an O(M^2 log^2 M) solution. We can further speed this up by noticing that
// we only need to check t where a[t] = max(a[i]) and t is the minimum and maximum i that
// is equal max(a[i]). Why? Since b[i] - a[i] is smaller the closer i is to t, let j not be
// in the common interval of all reversed intervals. Then b[t] - a[t] + 1 <= b[j] - a[j].
// If we assume a[t] + 1 <= a[j], we can sum them to get b[t] + 2 <= b[j]. But by definition
// b[t] = max(b[i]) or b[t] = max(b[i]) - 1, thus we get a contradiction. Therefore, a[t] =
// max(a[i]) must be satisfied.
//
// Now we prove the second condition (only checking the leftmost and rightmost t such that a[t] =
// max(a[i])). First, there is no reversed interval [x, y], such that l < x < y < r. Assume otherwise.
// Then, when we reverse [x, y], let b' be the resulting arrangement. We have b'[t] = b[t] + 1
// and b'[l] = b[l] - 1, and b'[l] >= b'[t] since we use t = l. Then we get b[l] >= b[t] + 2 which
// is a contradiction since b[t] = max(b[i]) or b[t] = max(b[i]) - 1. Thus no such [x, y] exist, which
// means we only need to consider t = l or t = r.
//
// After we determine max_ans and t, we can do the reversal greedily. We can use a segment tree or a
// priority queue to support the operations: point update += x at position i and remove x items from
// the right to simulate the greedy selection. We check after we do all flips to see if we satisfy
// everything.
//
// Time: O(N log^2 N)
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int N, M;
cin >> N >> M;
vector<int> A(M), B(M), C(M);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i] >> C[i];
A[i]--, B[i]--;
if (A[i] > B[i]) {
swap(A[i], B[i]);
}
}
vector<long long> sum(N);
vector<vector<pair<int, int>>> segs(N);
for (int i = 0; i < M; i++) {
sum[A[i]] += C[i];
sum[B[i]] -= C[i];
segs[A[i]].emplace_back(B[i], C[i]);
}
for (int i = 1; i < N; i++) {
sum[i] += sum[i - 1];
}
long long mx = *max_element(begin(sum), end(sum));
int ll = -1, rr = -1;
for (int i = 0; i < N; i++) {
if (sum[i] == mx) {
ll = i;
break;
}
}
for (int i = N - 1; i >= 0; i--) {
if (sum[i] == mx) {
rr = i;
break;
}
}
auto Check = [&](int t, long long mx, long long flips) -> bool {
vector<long long> upd_sum(N);
for (int i = 1; i < N; i++) {
upd_sum[i] += upd_sum[i - 1];
}
long long flipped = 0;
priority_queue<array<int, 3>> pq;
for (int pos = 0; pos <= t; pos++) {
for (auto i : segs[pos]) {
if (i.first > t) {
pq.push({i.first, pos, i.second});
}
}
// Look at effects to upd_sum for derivation, sum[pos] += 2 * constant
long long need = (sum[pos] - mx + flips + 1) / 2;
if (pos == t) need = flips;
need = max(need - flipped, 0ll);
flipped += need;
while (need > 0) {
if (pq.empty()) {
return false;
}
auto arr = pq.top(); pq.pop();
long long del = min(need, 1ll * arr[2]);
arr[2] -= del, need -= del;
if (arr[2] > 0) {
pq.push(arr);
}
// Add [0, A) and [B, N)
upd_sum[0] += del;
upd_sum[arr[1]] -= del;
upd_sum[arr[0]] += del;
// Undo [A, B)
upd_sum[arr[1]] -= del;
upd_sum[arr[0]] += del;
}
}
for (int i = 0; i < N; i++) {
if (i > 0) {
upd_sum[i] += upd_sum[i - 1];
}
if (sum[i] + upd_sum[i] > mx) {
return false;
}
}
return true;
};
auto CheckAll = [&](long long m) -> bool {
return Check(ll, m, sum[ll] - m + 0) ||
Check(ll, m, sum[ll] - m + 1) ||
Check(rr, m, sum[rr] - m + 0) ||
Check(rr, m, sum[rr] - m + 1);
};
long long lo = 0, hi = mx;
while (lo < hi) {
long long md = (lo + hi) / 2;
if (CheckAll(md)) {
hi = md;
} else {
lo = md + 1;
}
}
cout << lo << "\n";
return 0;
}
