#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
#define int ll
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pair<pair<int, int>, int>> v;
map<pair<int, int>, int> mp;
rep(i, 0, m) {
int a, b, c;
cin >> a >> b >> c;
a--; b--;
if(a > b) swap(a, b);
b--;
mp[{a, b}] += c;
}
repIn(i, mp) v.pb(i);
m = v.size();
pair<int, int> mx = {-1, -1};
vector<int> over;
vector<pair<int, int>> begs, ends;
repIn2(ab, c, v) begs.pb({ab.first, c}), ends.pb({ab.second, c});
ranges::sort(begs), ranges::sort(ends);
int bi = 0, ei = 0;
int cur = 0;
rep(i, 0, n) {
while(bi < m && begs[bi].first <= i) cur += begs[bi++].second;
while(ei < m && ends[ei].first < i) cur -= ends[ei++].second;
mx = max(mx, {cur, i});
over.pb(cur);
}
int l = 0, r = mx.first;
while(r - l > 1) {
int md = (l + r) / 2;
bool works = false;
rep(out, mx.first - md, mx.first - md + 2) {
// over + out - 2x <= md
// 2x >= over + out - md
// x >= (over + out - md) / 2
priority_queue<pair<int, int>> q;
int vi = 0, turned = 0;
vector<pair<int, int>> whereTo;
bool g = true;
rep(i, 0, mx.second + 1) {
while(vi < m && v[vi].first.first <= i) {
if(v[vi].first.second >= mx.second) q.push({v[vi].first.second, v[vi].second});
vi++;
}
int need = (over[i] + out - md + 1) / 2;
while(q.size() && turned < need) {
auto [end, val] = q.top();
q.pop();
if(val <= need - turned) {
turned += val;
whereTo.pb({end, val});
}
else {
whereTo.pb({end, need - turned});
val -= need - turned;
turned = need;
q.push({end, val});
}
}
if(turned < need) { g = false; break; }
}
if(!g) continue;
ranges::sort(whereTo);
int wti = 0;
rep(i, mx.second + 1, n) {
while(wti < (int)whereTo.size() && whereTo[wti].first < i) turned -= whereTo[wti++].second;
int need = (over[i] + out - md + 1) / 2;
if(turned < need) { g = false; break; }
}
if(!g) continue;
works = true;
// TODO maybe check n?
break;
}
(works ? r : l) = md;
}
cout << r << eol;
}
