#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
struct tr {
int l, r;
ll c;
};
const int MAXN = 2e5 + 7;
int n, m;
tr T[MAXN];
ll ile[MAXN];
ll dod[MAXN];
ll dod2[MAXN];
ll policz[MAXN];
ll policz2[MAXN];
vector<pair<int, int>> jakie[MAXN];
bool check(ll f, ll k, int kt) {
// cout << "k = " << k << '\n';
// cout << "f = " << f << '\n';
rep(i, m + 1) {
ile[i] = T[i].c;
}
rep(i, n + 2) {
jakie[i].clear();
dod2[i] = dod[i];
policz2[i] = 0ll;
}
priority_queue<pair<int, int>> pq;
rep(i, m) {
if (T[i].l <= kt && T[i].r >= kt) {
jakie[T[i].l].pb({T[i].r, i});
}
}
ll pol = 0;
for (int i = 0; i <= kt; i++) {
ll liczba = max(0ll, (policz[i] - pol - k + f)/2);
for (auto par: jakie[i]) {
pq.push(par);
}
// cout << "liczba = " << liczba << '\n';
while (liczba > 0) {
if (pq.empty()) {
return false;
}
pair<int, int> p = pq.top();
pq.pop();
int l = T[p.nd].l;
int r = T[p.nd].r;
ll spp = 0;
if (ile[p.nd] <= liczba) {
liczba -= ile[p.nd];
spp = ile[p.nd];
ile[p.nd] = 0;
}
else {
ile[p.nd] -= liczba;
spp = liczba;
liczba = 0ll;
pq.push(p);
}
f -= spp;
dod2[l] -= spp;
dod2[r + 1] += spp;
dod2[0] += spp;
dod2[l] -= spp;
dod2[r + 1] += spp;
}
}
ll s = 0;
rep(i, n + 1) {
s += dod2[i];
policz2[i] = s;
if (s > k) {
return false;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
rep(i, m) {
cin >> T[i].l >> T[i].r >> T[i].c;
if (T[i].l > T[i].r) {
swap(T[i].l, T[i].r);
}
dod[T[i].l] += T[i].c;
dod[T[i].r] -= T[i].c;
T[i].r--;
}
policz[0] = 0;
for (int i = 1; i < n; i++) {
policz[i] = policz[i - 1] + dod[i];
}
rep(i, n + 1) {
dod[i] = 0;
}
ll x = 0;
int kt = 0;
rep(i, n) {
if (policz[i] >= x) {
x = policz[i];
kt = i;
}
}
ll poc = 1;
ll kon = x;
ll odp = x;
// cout << "x = " << x << '\n';
while (poc < kon) {
ll sr = (poc + kon)/2;
if (check(x - sr, sr, kt) || check(x - sr + 1, sr, kt)) {
odp = sr;
kon = sr;
}
else {
poc = sr + 1;
}
}
cout << odp << '\n';
return 0;
}
