#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll,ll>
const ll MAXN = 2e5 + 5;
ll n, m;
ll V[MAXN];
ll V2[MAXN];
struct d{
ll a;
ll b;
ll c;
};
vector<d> ludzie[MAXN];
struct comp{
bool operator()(const d &p1, const d &p2){
if(p1.b != p2.b) return p1.b < p2.b;
return false;
}
};
bool czy(ll F, ll k, ll koniec){
//cout << F << " " << k << " " << koniec << " BS\n";
ll pom = 0;
priority_queue<d, vector<d>, comp> pq;
for(ll i = 1; i <= n; ++i){
V2[i] = 0;
}
for(ll i = 1; i <= koniec; ++i){
for(auto u : ludzie[i]){
if(u.b >= koniec){
pq.push(u);
}
}
ll ile = max(0ll, (V[i] - pom - k + F + 1) / 2);
while(ile > 0){
if(pq.empty()) return false;
auto e = pq.top();
pq.pop();
ll plus;
if(ile >= e.c){
plus = e.c;
ile -= e.c;
}
else{
plus = ile;
ile = 0;
pq.push({e.a, e.b, e.c - plus});
}
F -= plus;
pom += plus;
V2[e.a] -= 2 * plus;
V2[e.b+1] += 2 * plus;
V2[0] += plus;
}
}
for(ll i = 1; i <= n; ++i){
V2[i] += V2[i-1];
if(V2[i] > k) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
ll a, b, c;
for(ll i = 0; i < m; ++i){
cin >> a >> b >> c;
if(a > b) swap(a, b);
b--;
ludzie[a].push_back((d){a, b, c});
V[a] += c;
V[b+1]-= c;
}
ll mx = 0;
ll ind = -1;
for(ll i = 1; i <= n; ++i){
V[i] += V[i - 1];
// cout << V[i] << " ";
if(V[i] >= mx){
mx = V[i];
ind = i;
}
}
ll p = 1;
ll k = mx;
while(p != k){
ll sr = (p + k) / 2;
if(czy(mx - sr, sr, ind) or czy(mx - sr + 1, sr, ind)){
k = sr;
}
else{
p = sr + 1;
}
}
cout << p << "\n";
return 0;
}
