#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
#define int ll
const int inf = 1e9;
const ll infl = 1e18;
int n,m;
vector<array<int,3>> frag;
vector<array<int,3>> ev;
vector<array<int,3>> bett;
ll val[200000];
ll need[200000];
pair<ll,int> mx = {-1,-1};
bool solve(ll k)
{
ll dn = val[mx.nd]-k;
//cerr<<dn<<"\n";
rep(tt,2)
{
rep(i,n-1)
{
need[i] = (val[i] - k + dn + 1)/2;
// cerr<<need[i]<<" ";
}
//cerr<<"\n";
priority_queue<pair<int,ll>> pq;
ll cv = 0;
priority_queue<pair<int,ll>,vector<pair<int,ll>>,greater<pair<int,ll>>> ev;
int j = 0;
ll am = 0;
bool exit = false;
rep(i,n-1)
{
//if(!ev.empty())cerr<<i<<" "<<ev.top().st<<" "<<ev.top().nd<<" "<<"\n";
while(j != bett.size() && bett[j][0] == i)
{
pq.push({bett[j][1],bett[j][2]});
j++;
}
while(!ev.empty() && ev.top().st == i)
{
cv -= ev.top().nd;
ev.pop();
}
while(cv < need[i])
{
if(!pq.empty())
{
if(pq.top().st < i)
{
pq.pop();
continue;
}
if(cv + pq.top().nd <= need[i])
{
ev.push({pq.top().st+1,pq.top().nd});
cv += pq.top().nd;
am += pq.top().nd;
//cerr<<am<<" "<<cv<<" "<<pq.top().st<<" "<<pq.top().nd<<"\n";
pq.pop();
}
else
{
pair<int,int> cc = pq.top();
pq.pop();
ev.push({pq.top().st+1,need[i] - cv});
pq.push({pq.top().st,pq.top().nd - (need[i] - cv)});
am += need[i] - cv;
cv = need[i];
//cerr<<am<<" "<<cv<<" "<<pq.top().st<<" "<<pq.top().nd<<"\n";
}
}
else
{
exit = true;
}
if(am > dn)
{
exit = true;
}
if(exit) break;
}
//cerr<<i<<" "<<cv<<"\n";
if(exit) break;
}
if(!exit)
{
return 1;
}
dn++;
}
return 0;
}
int32_t main()
{
cin>>n>>m;
frag.resize(m);
rep(i,m)
{
int a,b,c;
cin>>a>>b>>c;
a--;b--;
if(a > b)
{
swap(a,b);
}
b--;
frag[i] = {a,b,c};
}
sort(all(frag));
rep(i,m)
{
ev.pb({frag[i][0],1,frag[i][2]});
ev.pb({frag[i][1] + 1,-1,frag[i][2]});
}
sort(all(ev));
int j = 0;
ll cu = 0;
rep(i,n-1)
{
while(j != m*2 && ev[j][0] == i)
{
cu += ev[j][1] * ev[j][2];
j++;
}
val[i] = cu;
if(cu > mx.st)
{
mx.st = cu;
mx.nd = i;
}
}
rep(i,m)
{
if(frag[i][0] <= mx.nd && mx.nd <= frag[i][1])
{
bett.pb(frag[i]);
//cerr<<bett.back()[0]<<" "<<bett.back()[1]<<" "<<bett.back()[2]<<"\n";
}
}
//cerr<<mx.st<<" "<<mx.nd<<"\n";
//cerr<<solve(1)<<"\n";
ll l = 0;
ll r = infl;
while(l + 1 < r)
{
ll mid = (l+r)/2;
if(solve(mid))
{
r = mid;
}
else
{
l = mid;
}
}
cout<<r<<"\n";
}
