#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool czy(ll x, ll k, vector<vector<pair<ll, ll>>> &w, vector<ll> &sum, ll mx, ll poz, ll n, ll m) {
vector<ll> wzor (n+1, 0);
for (ll i = 1; i <= n; i++) {
wzor[i] = sum[i]-x+(k-sum[i]+x+1)/2;
}
priority_queue<pair<ll, ll>> pq;
int s = 0;
vector<ll> z (n+2, 0);
for (int i = 1; i <= poz; i++) {
for (auto q : w[i]) {
pq.push(q);
}
ll su = -s;
while (!pq.empty() && su < wzor[i]) {
auto q = pq.top();
pq.pop();
int f = min(q.second, wzor[i]-su);
su += f;
s -= f;
z[q.first+1] += 2*f;
if (f < q.second) {
pq.push({q.first, q.second-f});
}
}
if (su < wzor[i]) return 0;
}
for (int i = poz+1; i <= n; i++) {
s += z[i];
if (s+sum[i] > x) {
return 0;
}
}
return 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll n, m;
cin >> n >> m;
vector<pair<pair<ll, ll>, ll>> k (m);
vector<ll> sum (n+2);
for (ll i = 0; i < m; i++) {
cin >> k[i].first.first >> k[i].first.second >> k[i].second;
if (k[i].first.first > k[i].first.second) {
swap(k[i].first.first, k[i].first.second);
}
k[i].first.second--;
sum[k[i].first.first]+=k[i].second;
sum[k[i].first.second+1]-=k[i].second;
}
ll mx = 0, poz = 0;
for (ll i = 1; i <= n; i++) {
sum[i] += sum[i-1];
if (sum[i] > mx) {
mx = sum[i];
poz = i;
}
}
vector<vector<pair<ll, ll>>> w (n+1);
for (int i = 0; i < m; i++) {
if (k[i].first.second >= poz && k[i].first.first <= poz) {
w[k[i].first.first].push_back({k[i].first.second, k[i].second});
}
}
ll b = 0, e = mx;
while (b < e) {
ll s = (b + e) / 2;
if (czy(s, mx - s, w, sum, mx, poz, n, m) || czy(s, mx - s + 1, w, sum, mx, poz, n, m)) e = s;
else b = s + 1;
}
cout << b << '\n';
}
