#include<cstdio>
#include<algorithm>
#define SZ 262144
using namespace std;
int n, m;
struct point {
int a, b, c;
bool operator <(point &p)const {
return a < p.a;
}
}w[201000];
long long S[201000], Z[201000], H[201000];
struct Tree {
long long Mn[SZ + SZ], K[SZ + SZ];
void UDT(int nd) {
Mn[nd] = min(Mn[nd * 2], Mn[nd * 2 + 1]);
}
void init(int nd, int b, int e) {
K[nd] = 0;
if (b == e) {
Mn[nd] = H[b];
return;
}
int m = (b + e) >> 1;
init(nd * 2, b, m);
init(nd * 2 + 1, m + 1, e);
UDT(nd);
}
void Add2(int nd, int x) {
Mn[nd] += x;
K[nd] += x;
}
void Spread(int nd) {
Add2(nd * 2, K[nd]);
Add2(nd * 2 + 1, K[nd]);
K[nd] = 0;
}
void Add(int nd, int b, int e, int s, int l, int x) {
if (s > l)return;
if (s <= b && e <= l) {
Add2(nd, x);
return;
}
Spread(nd);
int m = (b + e) >> 1;
if (s <= m)Add(nd * 2, b, m, s, l, x);
if (l > m)Add(nd * 2 + 1, m + 1, e, s, l, x);
UDT(nd);
}
long long Min(int nd, int b, int e, int s, int l) {
if (s > l)return (long long)1e18;
if (s <= b && e <= l)return Mn[nd];
Spread(nd);
int m = (b + e) >> 1;
long long r = 1e18;
if (s <= m)r = min(Min(nd * 2, b, m, s, l), r);
if (l > m)r = min(Min(nd * 2 + 1, m + 1, e, s, l), r);
return r;
}
}T;
int pv;
long long Get() {
int i;
T.init(1, 0, n - 1);
long long res = 0;
for (i = 1; i <= m; i++) {
long long t = min(min(T.Min(1, 0, n - 1, 0, w[i].a - 1), T.Min(1, 0, n - 1, w[i].b, n - 1)), (long long)w[i].c);
res += t;
T.Add(1, 0, n - 1, 0, w[i].a - 1, -t);
T.Add(1, 0, n - 1, w[i].b, n - 1, -t);
}
return res;
}
bool Pos(long long M) {
long long i, j;
long long bb = Z[pv] - M, ee = M / 2;
for (i = bb; i <= bb + 1; i++) {
for (j = 0; j < n; j++) {
H[j] = (i + M - Z[j]) / 2;
}
if (H[0] < i)continue;
if (Get() >= i)return true;
}
return false;
}
int main() {
int i;
//freopen("input.txt","r",stdin);
scanf("%d%d", &n, &m);
for (i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (a > b)swap(a, b);
w[i] = { a,b,c };
S[a] += c;
S[b] -= c;
}
sort(w + 1, w + m + 1);
long long Mx = -1;
pv = -1;
for (i = 1; i < n; i++) {
S[i] += S[i - 1];
if (Mx < S[i]) {
Mx = S[i];
pv = i;
}
}
for (i = 1; i <= pv; i++)Z[i] = max(Z[i - 1], S[i]);
for (i = n - 1; i >= pv; i--)Z[i] = max(Z[i + 1], S[i]);
long long b = 0, e = Mx - 1, mid, r = Mx;
while (b <= e) {
mid = (b + e) >> 1;
if (Pos(mid)) {
r = mid;
e = mid - 1;
}
else b = mid + 1;
}
printf("%lld\n", r);
}
