// https://www.luogu.com.cn/article/lqa8q1lu
// https://oj.uz/submission/684837
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
vector<long long> a(n);
vector<array<int, 3>> cands(m);
for (int i = 0; i < m; ++i) {
int l, r, c; cin >> l >> r >> c;
if (l > r) {
swap(l, r);
}
--l, --r;
a[l] += c;
a[r] -= c;
cands[i] = {l, r, c};
}
for (int i = 1; i <= n; ++i) {
a[i] += a[i - 1];
}
auto qry = [&](int k) {
fill(a.begin(), a.end(), 0);
priority_queue<array<int, 2>> pq;
long long res = 0;
for (int i = 0, j = 0; i < n; ++i) {
while (j < m && cands[j][0] == i) {
auto [l, r, c] = cands[j++];
a[l] += c;
a[r] -= c;
pq.push({r, c});
}
if (i) {
a[i] += a[i - 1];
}
while (a[i] > k) {
auto [r, c] = pq.top(); pq.pop();
long long x = min((long long) c, (a[i] - k + 1) / 2);
c -= x;
a[i] -= 2 * x;
a[r] += 2 * x;
res += x;
if (c) {
pq.push({r, c});
}
}
}
return res + k;
};
int p = max_element(a.begin(), a.end()) - a.begin();
for (int i = 0; i < m; ++i) {
auto &[l, r, c] = cands[i];
l = (l - p - 1 + n) % n;
r = (r - p - 1 + n) % n;
if (l > r) {
swap(l, r);
}
}
sort(cands.begin(), cands.end());
cout << min(qry(0), qry(1));
return 0;
}
