#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2e5 + 5;
typedef long long ll;
priority_queue< pair<int,int> > heap;
ll start[Nmax], finish[Nmax], add[Nmax], dp[Nmax], s[Nmax];
vector< pair<int,int> > v[Nmax];
int n, m, i, A, B;
struct Edge
{
int x, y, c;
};
vector< Edge > edges;
int mod(int x)
{
if(x <= 0) return x+n;
if(x>n) return x-n;
return x;
}
bool check_center(int where, ll L)
{
int i;
ll need = 0;
for(i=1; i<=n; ++i) v[i].clear();
for(i=1; i<=n; ++i) start[i] = 0, finish[i] = 0, add[i] = 0;
while(heap.size()) heap.pop();
for(auto e : edges)
{
int x, y;
x = mod(e.x - where + 1);
y = mod(e.y - where + 1);
if(x > y) swap(x, y);
v[x].push_back({y, e.c});
start[x] += e.c;
finish[y] += e.c;
}
dp[0] = L;
for(i=1; i<n; ++i)
{
for(auto it : v[i]) heap.push(it);
dp[i] = dp[i-1] + start[i] - finish[i] + add[i];
while(dp[i] > L)
{
assert(heap.size());
auto el = heap.top();
heap.pop();
if(dp[i] - 2 * el.second >= L)
{
dp[i] -= 2 * el.second;
add[el.first] += 2 * el.second;
need += el.second;
}
else
{
ll cat = (dp[i] - L + 1) / 2;
dp[i] -= 2 * cat;
add[el.first] += 2 * cat;
need += cat;
heap.push({el.first, el.second - cat});
}
}
if(need > L) return 0;
}
return (need <= L);
}
bool check(ll L)
{
return (check_center(A, L) || check_center(B, L));
}
int best_point(bool dir)
{
int i;
for(i=1; i<=n; ++i) s[i] = 0;
for(auto e : edges)
if(dir == 0)
{
s[e.x] += e.c;
s[e.y] -= e.c;
}
else
{
s[e.y] += e.c;
s[1] += e.c;
s[e.x] -= e.c;
}
for(i=1; i<=n; ++i) s[i] += s[i-1];
ll Max = 0;
for(i=1; i<=n; ++i) Max = max(Max, s[i]);
for(i=1; i<=n; ++i)
if(Max == s[i]) return mod(i+1);
}
int main()
{
// freopen("input", "r", stdin);
cin >> n >> m;
int i, x, y, C;
for(i=1; i<=m; ++i)
{
cin >> x >> y >> C;
if(x > y) swap(x, y);
edges.push_back({x, y, C});
}
A = best_point(0);
B = best_point(1);
ll st = 0, dr = m * (1e9), mid;
while(st <= dr)
{
mid = (st+dr) / 2;
if(check(mid)) dr = mid - 1;
else st = mid + 1;
}
cout << st << '\n';
return 0;
}
