#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MN = 200010;
int N, M;
ll cnt[MN];
vector<pair<ll, int> > stk;
vector<pii> V[MN];
struct BIT {
vector<ll> tree, lazy;
void init() {
tree = vector<ll>(4 * N);
lazy = vector<ll>(4 * N, 0);
build(0, N - 1, 1);
}
void build(int l, int r, int n) {
if(l == r) {
tree[n] = cnt[l];
return;
}
int m = (l + r)>>1;
build(l, m, 2*n);
build(m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 1]);
}
void prop(int l, int r, int n) {
if(l != r) {
tree[2*n] += lazy[n];
lazy[2*n] += lazy[n];
tree[2*n + 1] += lazy[n];
lazy[2*n + 1] += lazy[n];
lazy[n] = 0;
}
}
void upd(int a, int b, ll d, int l, int r, int n) {
if(b < l || r < a) return;
if(a <= l && r <= b) {
tree[n] += d;
lazy[n] += d;
return;
}
prop(l, r, n);
int m = (l + r)>>1;
upd(a, b, d, l, m, 2*n);
upd(a, b, d, m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 1]);
}
ll quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return 0;
if(a <= l && r <= b) return tree[n];
prop(l, r, n);
int m = (l + r)>>1;
ll L = quer(a, b, l, m, 2*n);
ll R = quer(a, b, m + 1, r, 2*n + 1);
return max(L, R);
}
} bit;
struct Info {
int a, b, c;
bool operator <(const Info &i) const {
return b < i.b;
}
};
priority_queue<Info> pq;
bool check(ll bound) {
bit.init();
while(!pq.empty()) pq.pop();
int pos = 0;
for(int i = 0; i < stk.size(); i++) {
while(pos <= stk[i].second) {
for(int j = 0; j < V[pos].size(); j++) {
pq.push({ pos, V[pos][j].first, V[pos][j].second });
}
pos++;
}
int x = stk[i].second;
ll t = bit.quer(x, x, 0, N - 1, 1);
ll d = bit.tree[1];
ll need = max(0LL, (t + d - 2 * bound + 1) / 2);
while(need && !pq.empty()) {
Info t = pq.top(); pq.pop();
ll mn = min(need, 1LL * t.c);
need -= mn;
t.c -= mn;
if(t.c) pq.push(t);
bit.upd(0, N - 1, mn, 0, N - 1, 1);
bit.upd(t.a, t.b, -2 * mn, 0, N - 1, 1);
}
if(need) return false;
if(bit.tree[1] <= bound) return true;
}
return false;
}
int main() {
scanf("%d %d", &N, &M);
ll sum = 0;
for(int i = 0; i < M; i++) {
int a, b, c; scanf("%d %d %d", &a, &b, &c);
a--; b--;
if(a > b) swap(a, b);
b--;
cnt[a] += c;
cnt[b + 1] -= c;
V[a].push_back(pii(b, c));
sum += c;
}
for(int i = 1; i < N; i++) cnt[i] += cnt[i - 1];
for(int i = N - 1; i >= 0; i--) {
while(!stk.empty() && stk.back().first <= cnt[i]) stk.pop_back();
stk.push_back({cnt[i], i});
}
reverse(stk.begin(), stk.end());
ll s = 0, e = sum, p = -1;
while(s <= e) {
ll m = (s + e)>>1;
if(check(m)) {
p = m;
e = m - 1;
}
else s = m + 1;
}
printf("%lld", p);
}
