#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 200000;
ll const inf = 1000000000000000000;
struct Person{
int x;
int y;
int cost;
bool operator < (Person const &a) const {
return y < a.y;
}
} v[1 + nmax];
class SegmentTree{
private:
vector<ll> aint;
vector<ll> lazy;
public:
SegmentTree(int n){
aint.resize(1 + 4 * n);
lazy.resize(1 + 4 * n);
}
void cleannode(int node, int from, int to){
if(lazy[node] == 0)
return ;
if(from < to){
int mid = (from + to) / 2;
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
aint[node] += lazy[node];
lazy[node] = 0;
}
void computenode(int node, int from, int to){
aint[node] = max(aint[node * 2], aint[node * 2 + 1]);
}
void update(int node, int from, int to, int x, int y, ll val){
if(from == x && to == y){
lazy[node] += val;
cleannode(node, from, to);
} else {
int mid = (from + to) / 2;
cleannode(node * 2, from, mid);
cleannode(node * 2 + 1, mid + 1, to);
if(x <= mid)
update(node * 2, from, mid, x, MIN(y, mid), val);
if(mid + 1 <= y)
update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
computenode(node, from, to);
}
}
int query(int node, int from, int to, int x, int y){
cleannode(node, from, to);
if(from == x && to == y)
return aint[node];
else {
int mid = (from + to) / 2;
if(x <= mid && y <= mid)
return query(node * 2, from, mid, x, y);
else if(mid + 1 <= x && mid + 1 <= y)
return query(node * 2 + 1, mid + 1, to, mid + 1, y);
else
return max(query(node * 2, from, mid, x, mid), query(node * 2 + 1, mid + 1, to, mid + 1, y));
}
}
};
int eval(int n, int q, ll target){
SegmentTree aint(n);
for(int i = 1;i <= q; i++){
ll acc = min((target - aint.query(1, 1, n, v[i].x, v[i].y - 1)), 1LL * v[i].cost);
aint.update(1, 1, n, v[i].x, v[i].y - 1, acc);
if(1 < v[i].x)
aint.update(1, 1, n, 1, v[i].x - 1, v[i].cost - acc);
if(v[i].y <= n)
aint.update(1, 1, n, v[i].y, n, v[i].cost - acc);
if(target < aint.query(1, 1, n, 1, n))
return 0;
}
return 1;
}
int binarysearch(ll from, ll to, int n, int q){
if(from < to){
ll mid = (from + to) / 2;
if(eval(n, q, mid) == 1)
return binarysearch(from, mid, n, q);
else
return binarysearch(mid + 1, to, n, q);
} else
return from;
}
int main()
{
int n, q;
cin >> n >> q;
for(int i = 1;i <= q; i++){
cin >> v[i].x >> v[i].y >> v[i].cost;
if(v[i].y < v[i].x)
swap(v[i].x, v[i].y);
}
sort(v + 1, v + q + 1);
cout << binarysearch(1, inf, n, q);
return 0;
}
