#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<17;
pair<int, int> tab[N];
ll il[N];
ll lft[N];
ll drz[2 * N], laz[2 * N];
void Add(int v, int p, int k, int pz, int kz, ll x)
{
if(p > kz || k < pz) return;
if(p >= pz && k <= kz)
{
laz[v] += x; drz[v] += x;
return;
}
Add(v * 2, p, (p + k) / 2, pz, kz, x);
Add(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
}
inline void A(int a, int b, ll x)
{
if(a <= b)
Add(1, 0, N - 1, a, b, x);
}
ll Query(int v, int p, int k, int pz, int kz)
{
if(p > kz || k < pz) return 0LL;
if(p >= pz && k <= kz)
return drz[v];
ll a = Query(v * 2, p, (p + k) / 2, pz, kz);
a = max(a, Query(v * 2, p, (p + k) / 2, pz, kz));
return a + laz[v];
}
inline ll Q(int a, int b)
{
if(a > b) return 0LL;
return Query(1, 0, N - 1, a, b);
}
ll Val(int v)
{
v += N;
ll ans = drz[v];
v /= 2;
while(v > 0)
{
ans += laz[v];
v /= 2;
}
return ans;
}
bool Check(int n, int m, ll x)
{
for(int i = 1; i <= m; ++i)
{
drz[tab[i].st + N] += il[i];
drz[tab[i].nd + N] -= il[i];
laz[i + N] = 0;
}
for(int i = N + 1; i <= N + n; ++i)
drz[i] += drz[i - 1];
for(int i = N - 1; i >= 1; --i)
{
drz[i] = drz[i * 2] + drz[i * 2 + 1];
laz[i] = 0;
}
priority_queue<pair<pair<int, int>, int>> q;
int j = 0;
for(int i = 1; i <= n; ++i)
{
while(j < m && tab[j + 1].st >= i)
{
++j;
q.push(make_pair(make_pair(tab[j].nd, -tab[j].st), j));
lft[j] = il[j];
}
ll cur = Val(i);
//cout << "POS: " << i << " " << cur << "\n";
while((int)q.size() > 0 && cur > x)
{
if(q.top().st.st <= i) {q.pop(); continue;}
int b = q.top().st.st, a = -q.top().st.nd, l = q.top().nd;
lft[l] = min(lft[l], x - max(Q(1, a - 1), Q(b, n)));
//cerr << "C: " << a << " " << b << " " << l << " " << lft[l] << " " << cur << "\n";
ll d = min(cur - x, lft[l]);
cur -= d;
lft[l] -= d;
A(a, b - 1, -d);
A(1, a - 1, d);
A(b, n, d);
if(lft[l] == 0LL)
q.pop();
}
if(cur > x) return 0;
}
return 1;
}
ll BS(int n, int m, ll lim)
{
ll p = 1LL, k = lim, s;
while(p < k)
{
s = (p + k) / 2;
if(Check(n, m, s))
k = s;
else
p = s + 1;
}
return p;
}
void Solve()
{
int n, m; ll lim = 0LL;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> tab[i].st >> tab[i].nd >> il[i];
if(tab[i].st > tab[i].nd)
swap(tab[i].st, tab[i].nd);
lim += il[i];
}
//cout << Check(n, m, 3) << "\n";
ll ans = 0LL;
ans = BS(n, m, lim);
cout << ans << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t;
//while(t--)
Solve();
return 0;
}
