#include <stdio.h>
#include <string.h>
#define N 200000
#define M 100000
#define INF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int main() {
static int ll[M], rr[M], cc[M];
static long long ww[N], dd[N], dd_[N];
int n, m, h, i, j, r, tmp;
long long w, x, y, z, ans;
scanf("%d%d", &n, &m), n--;
x = 0;
for (h = 0; h < m; h++) {
scanf("%d%d%d", &ll[h], &rr[h], &cc[h]), ll[h]--, rr[h]--;
if (ll[h] > rr[h])
tmp = ll[h], ll[h] = rr[h], rr[h] = tmp;
dd[ll[h]] += cc[h], dd[rr[h]] -= cc[h];
x += cc[h];
}
for (i = 1; i < n; i++)
dd[i] += dd[i - 1];
w = -INF;
for (i = 0; i < n; i++)
w = max(w, -dd[i]);
for (i = 0; i < n; i++)
ww[i] = w + dd[i];
ans = INF;
for (r = 0; r < 2; r++) {
y = INF;
for (i = 0; i < n; i++)
y = min(y, x - dd[i] + (ww[i] + r) / 2);
z = INF;
for (i = 0; i < n; i++) {
memset(dd_, 0, (n + 1) * sizeof *dd_);
for (h = 0; h < m; h++)
if (ll[h] > i)
dd_[ll[h]] += cc[h], dd_[rr[h]] -= cc[h];
for (j = 1; j < n; j++)
dd_[j] += dd_[j - 1];
for (j = i + 1; j < n; j++)
z = min(z, x - dd[i] - dd_[j] + (ww[i] + r) / 2 + (ww[j] + r) / 2);
}
ans = min(ans, x - min(min(x, y), z) + w + r);
}
printf("%lld\n", ans);
return 0;
}
