#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];
bool spr(long long sr, long long ilezw)
{
priority_queue<pair<long long, long long>> pq;
long long suma = 0;
for(long long i = 0; i < n + 3; i++)
{
sumakon[i] = 0;
}
long long cur = 0;
long long usunl = 0;
for(long long i = 1; i <= gdziemax; i++)
{
for(auto x : przechodzace[i])
{
pq.push(x);
cur += x.second;
suma += x.second;
sumakon[x.first] += x.second;
}
while(cur > sr)
{
auto x = pq.top();
pq.pop();
long long minn = min(cur - sr, x.second);
x.second -= minn;
cur -= minn;
usunl += minn;
if(x.second > 0)
{
pq.push(x);
}
}
}
while(!pq.empty())
{
pq.pop();
}
cur = 0;
long long usup = 0;
for(long long j = gdziemax; j <= n - 1; j++)
{
if(sumakon[j] > 0)
{
long long remain = sumakon[j];
while(remain > 0)
{
pq.push({j, remain});
cur += remain;
remain = 0;
}
}
while(cur > sr)
{
auto x = pq.top();
pq.pop();
long long minn = min(cur - sr, x.second);
x.second -= minn;
cur -= minn;
usup += minn;
if(x.second > 0)
{
pq.push({x.first, x.second});
}
}
}
if(usunl + usup <= suma)
{
return true;
}
else
{
return false;
}
}
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;
}
}
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;
}
}
cout << l << endl;
return 0;
}
