#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<17;
pair<pair<int, int>, ll> tab[N];
ll sum[N];
ll nw[N];
int pos = 0;
ll lft[N];
bool Try(int n, int m, ll ilo, ll x)
{
priority_queue<pair<int, int>> q;
for(int i = 1; i <= n; ++i) nw[i] = 0LL;
ll s = 0LL;
int j = 0;
for(int i = 1; i <= pos; ++i)
{
while(j < m && tab[j + 1].st.st <= i)
{
++j;
if(tab[j].st.nd >= pos + 1)
q.push(make_pair(tab[j].st.nd, j));
lft[j] = tab[j].nd;
}
ll cr = (sum[i] - s - x) + ((ilo - s + 1LL - (sum[i] - s - x)) / 2LL);
//cout << i << " " << sum[i] << " " << s << " " << cr << "\n";
cr = max(cr, 0LL);
if(s + cr > ilo) return 0;
while((int)q.size() > 0 && cr > 0LL)
{
int l = q.top().nd;
ll d = min(cr, lft[l]);
//cout << "Q: " << l << " " << d << " " << cr << " " << tab[l].st.st << " " << tab[l].st.nd << " " << lft[l] << "\n";
lft[l] -= d;
cr -= d;
nw[1] += d; nw[tab[l].st.st] -= 2LL * d;
nw[tab[l].st.nd] += 2LL * d; nw[n + 1] -= d;
s += d;
if(lft[l] == 0LL)
q.pop();
}
if(cr > 0LL) return 0;
}
for(int i = 1; i <= n; ++i)
nw[i] += nw[i - 1];
for(int i = 1; i <= n; ++i)
{
nw[i] += sum[i];
//cout << nw[i] << "\n";
if(nw[i] > x) return 0;
}
return 1;
}
bool Check(int n, int m, ll x)
{
if(x >= sum[pos]) return 1;
if(Try(n, m, sum[pos] - x, x))
return 1;
if(Try(n, m, sum[pos] - x + 1LL, x))
return 1;
return 0;
}
ll BS(int n, int m, ll lim)
{
ll p = 1LL, k = lim, s;
while(p < k)
{
s = (p + k) / 2;
//cout << p << " " << k << " " << s << "\n";
if(Check(n, m, s))
k = s;
else
p = s + 1;
}
return p;
}
void Solve()
{
int n, m; ll lim = 0LL;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> tab[i].st.st >> tab[i].st.nd >> tab[i].nd;
if(tab[i].st.st > tab[i].st.nd)
swap(tab[i].st.st, tab[i].st.nd);
sum[tab[i].st.st] += tab[i].nd;
sum[tab[i].st.nd] -= tab[i].nd;
lim += tab[i].nd;
}
sort(tab + 1, tab + 1 + m);
ll ma = 0LL;
for(int i = 1; i <= n; ++i)
{
sum[i] += sum[i - 1];
if(sum[i] > ma)
{
pos = i; ma = sum[i];
}
}
//cout << Try(n, m, 2, 2LL) << "\n";
ll ans = 0LL;
ans = BS(n, m, lim);
cout << ans << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t;
//while(t--)
Solve();
return 0;
}
