// vaziat meshki-ghermeze !
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 4e5 + 10;
vector<pii> G[N];
int n, m;
void Add_Edge(int u, int v, int c){
G[u].pb({v, c});
}
ll ps[N];
ll Solve(int l, int dif){
int r = l + n;
memset(ps, 0, sizeof ps);
multiset<pii> ms;
ll res = 0;
for(int i = l; i < r - 1; i++){
for(auto [x, c] : G[i]){
if(x >= r) continue;
ps[i] += c;
ps[x] -= c;
ms.insert({x, c});
}
ps[i] += ps[i - 1];
while(ps[i] > dif){
auto [fr, cnt] = *ms.rbegin();
ms.erase(ms.find({fr, cnt}));
if(fr <= i)
continue;
int del = min((ll) cnt, (ps[i] - dif + 1) / 2);
ps[i] -= 2 * del;
ps[fr] += 2 * del;
res += del;
if(cnt > del)
ms.insert({fr, cnt - del});
}
}
return res + dif;
}
ll df[N];
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
int a, b, c;
for(int i = 0; i < m; i++){
cin >> a >> b >> c;
// assert(c == 1);
if(a > b) swap(a, b);
df[a] += c;
df[b] -= c;
Add_Edge(a, b, c);
Add_Edge(b, n + a, c);
Add_Edge(n + a, n + b, c);
}
for(int i = 1; i <= n; i++) df[i] += df[i - 1];
int id_mx = max_element(df + 1, df + n) - df;
id_mx ++;
ll ans = min(Solve(id_mx, 0), Solve(id_mx, 1));
cout << ans << '\n';
return 0;
}
