#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<long long, long long>, long long>> wyma;
long long roz[200007];
long long ile[200007];
long long sumakon[200007];
long long maxseg = -1, gdziemax, n, m;
vector<pair<long long, long long>> przechodzace[200007];
long long cof[200007];
long long gdziemax2;
bool spr(long long sr, long long ilezw)
{
if(ilezw < 0)
{
return false;
}
priority_queue<pair<long long, long long>> pq;
for(long long i = 0; i < n + 3; i++)
{
sumakon[i] = 0;
}
long long cur = 0;
long long zostalo = ilezw;
for(long long i = 1; i <= gdziemax; i++)
{
for(auto x : przechodzace[i])
{
pq.push(x);
}
while(ile[i] - cur + zostalo > sr)
{
if(pq.empty())
{
return false;
}
auto x = pq.top();
pq.pop();
long long potrzeb = ile[i] - cur + zostalo - sr;
long long minn = min(x.second, (potrzeb + 1) / 2);
cur += minn;
zostalo -= minn;
sumakon[x.first + 1] += 2 * minn;
x.second -= minn;
if(x.second > 0)
{
pq.push(x);
}
}
}
sumakon[gdziemax + 1] -= cur;
for(long long i = gdziemax + 1; i <= n; i++)
{
sumakon[i] += sumakon[i - 1];
if(ile[i] + sumakon[i] > sr)
{
return false;
}
}
return true;
}
long long policz(long long gdzie)
{
gdziemax = gdzie;
for(long long i = 0; i < n + 3; i++)
{
przechodzace[i].clear();
}
for(auto x : wyma)
{
if(x.first.first <= gdziemax && gdziemax <= x.first.second)
{
przechodzace[x.first.first].push_back({x.first.second, x.second});
}
}
long long l = 0, r = maxseg;
while(l < r)
{
long long sr = (l + r) / 2;
if(spr(sr, maxseg - sr) || spr(sr, maxseg - sr + 1))
{
r = sr;
}
else
{
l = sr + 1;
}
}
return l;
}
int main()
{
cin >> n >> m;
for(long long i = 0; i < m; i++)
{
long long a, b, c;
cin >> a >> b >> c;
if(a > b)
{
swap(a, b);
}
wyma.push_back({{a, b - 1}, c});
roz[a] += c;
roz[b] -= c;
}
for(long long i = 1; i <= n; i++)
{
ile[i] = ile[i - 1] + roz[i];
if(maxseg < ile[i])
{
maxseg = ile[i];
gdziemax = i;
}
if(maxseg == ile[i])
{
gdziemax2 = i;
}
}
cout << min(policz(gdziemax), policz(gdziemax2)) << endl;
return 0;
}
