#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef pair<int,int> pii;
const int MAXN = 4e5+5;
int N, M, st;
ll pref[MAXN], mn, ans;
vector <pii> seg[MAXN];
priority_queue <pii> PQ;
void solve() {
for (int i=st;i<=st+N;i++) {
pref[i] = 0;
}
while (!PQ.empty()) {
PQ.pop();
}
for (int i=st+1;i<=st+N;i++) {
pref[i] += pref[i-1];
for (auto x : seg[i]) {
if (x.fi > st+N) continue;
pref[i] += x.se;
pref[x.fi] -= x.se;
PQ.push(x);
}
while (pref[i] > ans) {
auto x = PQ.top();
PQ.pop();
int use = min((ll)x.se,(pref[i]-ans+1)/2);
if (use < x.se) {
PQ.push({x.fi,x.se-use});
}
ans += use;
pref[i] -= use;
pref[x.fi] += 2*use;
}
}
}
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
for (int i=1;i<=M;i++) {
int A, B, C;
cin >> A >> B >> C;
if (A > B) swap(A,B);
seg[A].push_back({B,C});
seg[B].push_back({N+A,C});
seg[N+A].push_back({N+B,C});
pref[A] += C;
pref[B] -= C;
}
for (int i=1;i<=N;i++) {
pref[i] += pref[i-1];
if (pref[i] > pref[st]) {
st = i;
}
}
solve();
mn = ans;
// ans = 1;
// solve();
cout << min(mn,ans) << "\n";
}
