#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
struct SegmentTree{
vector<ll> tree;
vector<ll> lazy;
void init(ll n) {
ll sz = 1 << __lg(n-1) + 2;
tree.assign(sz, 0);
lazy.assign(sz, 0);
}
void build(ll node, ll s, ll e, vector<ll> &v) {
if (s == e) {
tree[node] = v[s];
return;
}
ll mid = s + e >> 1;
build(node*2, s, mid, v);
build(node*2+1, mid+1, e, v);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
void propagate(ll node, ll s, ll e) {
tree[node] += lazy[node];
if (s != e) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
void update(ll node, ll s, ll e, ll l, ll r, ll v) {
propagate(node, s, e);
if (l > e || s > r) return;
if (l <= s && e <= r) {
lazy[node] = v;
propagate(node, s, e);
return;
}
ll mid = s + e >> 1;
update(node*2, s, mid, l, r, v);
update(node*2+1, mid+1, e, l, r, v);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
ll query(ll node, ll s, ll e, ll l, ll r) {
propagate(node, s, e);
if (l > e || s > r) return 0;
if (l <= s && e <= r) return tree[node];
ll mid = s + e >> 1;
return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
}
};
SegmentTree seg;
struct Move{
ll A, B, C;
};
ll N, M;
ll solve(ll X, vector<ll> &use, vector<Move> &a) {
seg.init(N);
seg.build(1, 0, N-1, use);
ll ans = 0;
for (ll i=0; i<M; i++) {
ll mx = seg.query(1, 0, N-1, a[i].A, a[i].B-1);
if (mx == X) continue;
seg.update(1, 0, N-1, a[i].A, a[i].B-1, min(a[i].C, (X - mx) / 2) * 2);
ans += min(a[i].C, (X - mx) / 2);
}
return ans;
}
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
cin >> N >> M;
vector<Move> a(M);
ll tot = 0;
for (ll i=0; i<M; i++) {
cin >> a[i].A >> a[i].B >> a[i].C;
a[i].A --; a[i].B --;
if (a[i].A > a[i].B) swap(a[i].A, a[i].B);
tot += a[i].C;
}
sort(a.begin(), a.end(), [&] (Move &u, Move &v) {
if (u.B == v.B) return u.A > v.A;
return u.B < v.B;
});
vector<ll> use(N, 0);
seg.init(N);
for (ll i=0; i<M; i++) {
seg.update(1, 0, N-1, a[i].B, N-1, a[i].C);
seg.update(1, 0, N-1, 0, a[i].A-1, a[i].C);
}
for (ll i=0; i<N; i++) {
use[i] = seg.query(1, 0, N-1, i, i);
}
ll lo = tot, hi = 2*tot;
ll ans = tot;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
if (hi - lo > 1e6) mid = (lo*2 + hi) / 3;
ll ret1 = mid - solve(mid, use, a);
ll ret2 = mid+1 - solve(mid+1, use, a);
/*if (ret1 == ret2) {
ll t = mid + 2;
while (true) {
ret2 = t - solve(t, use, a);
cout << t << ' ' << ret2 << '\n';
if (ret2 != ret1) break;
t ++;
}
}*/
ans = min({ans, ret1, ret2});
if (ret1 > ret2) {
lo = mid + 2;
}
else {
hi = mid - 1;
}
}
cout << ans << '\n';
}
