#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct seg
{
int l,r;
ll c;
};
int n,m;
vector<seg> segs;
ll sum[200001];
ll sum2[200001];
vector<pll> end_events[200001];
priority_queue<pll> pq;
bool solve(int max_ind, ll f, ll k)
{
pq = {};
ll cur_del = 0;
vector<seg> rev;
vector<pll> del;
rep(i,max_ind+1)
{
ll ile_del = (max(0LL,(sum[i]+f-2*cur_del)-k)+1)/2;
if(i == max_ind)
{
ile_del = f-cur_del;
}
cerr << i << " " << ile_del << " " << cur_del << " " << f << " "<< k<< " ile_del\n";
forall(it,end_events[i]) pq.push(it);
cur_del += ile_del;
while(ile_del > 0 && siz(pq) > 0)
{
pll t = pq.top();
pq.pop();
if(ile_del - segs[t.ss].c >= 0)
{
rev.pb(segs[t.ss]);
ile_del -= segs[t.ss].c;
}
else
{
rev.pb({segs[t.ss].l,segs[t.ss].r,ile_del});
segs[t.ss].c -= ile_del;
del.pb({t.ss,ile_del});
pq.push({segs[t.ss].r,t.ss});
ile_del = 0;
}
}
if(ile_del != 0)
{
forall(it,del)
{
segs[it.ff].c += it.ss;
}
return 0;
}
}
forall(it,del)
{
segs[it.ff].c += it.ss;
}
rep(i,n) sum2[i] = 0;
forall(it,rev)
{
sum2[0] += it.c;
sum2[it.l] += -2*it.c;
sum2[it.r+1] += 2*it.c;
}
ll cur_sum = 0;
rep(i,n)
{
cur_sum += sum2[i];
sum2[i] = cur_sum;
cerr << sum[i] << " " << sum2[i] << " sum2\n";
}
rep(i,n)
{
if(sum[i]+sum2[i] > k) return 0;
}
return 1;
}
bool check(ll k)
{
rep(i,n) end_events[i] = {};
rep(i,n) sum[i] = 0;
forall(it,segs)
{
sum[it.l]+=it.c;
sum[it.r+1]-=it.c;
}
ll cur_sum = 0;
rep(i,n)
{
cur_sum += sum[i];
sum[i] = cur_sum;
}
pll best = {-1,-1};
rep(i,n) best = max(best,{sum[i],i});
rep(i,m)
{
if(segs[i].l <= best.ss && segs[i].r >= best.ss) end_events[segs[i].l].pb({segs[i].r,i});
}
if(best.ff <= k) return 1;
cerr << k << " " << best.ff << " " << best.ss << " xd\n";
return solve(best.ss,best.ff-k,k) || solve(best.ss,best.ff-k+1,k);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
cin >> n >> m;
rep(i,m)
{
int a,b,c;
cin >> a >> b >> c;
a--;
b = (b-2+n)%n;
if(a > b) swap(a,b);
segs.pb({a,b,c});
}
ll l = 0;
ll r = 1e15;
ll ans = 0;
while(l <= r)
{
ll mid = (l+r)/2;
if(check(mid))
{
ans = mid;
r = mid-1;
}
else
{
l = mid+1;
}
}
cout << ans << "\n";
}
