#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
int BASE;
vector<int> tree[2];
vector<int> lazy;
int comb(int a , int b , int k)
{
if(k == 0)
return a + b;
return max(a , b);
}
void build(int n)
{
BASE = n;
while(__builtin_popcount(BASE) != 1)
BASE++;
fore(i , 2)
tree[i].assign(2*BASE , 0);
lazy.assign(2*BASE , 0);
}
void propag(int node , int x)
{
if(lazy[node] == 0)
return ;
forr(lt , 2*node , 2*node + 1)
{
lazy[lt]+=lazy[node];
tree[0][lt]+=lazy[node] * x;
tree[1][lt]+=lazy[node];
}
lazy[node] = 0;
}
void upd(int node , int s , int e , int l , int r , int v)
{
if(l <= s && e <= r)
{
lazy[node]+=v;
tree[0][node]+=v * (e - s + 1);
tree[1][node]+=v;
return ;
}
if(l > e || s > r)
return;
propag(node , (e - s + 1)/2);
int mid = (s + e)>>1;
upd(2*node , s , mid , l , r , v);
upd(2*node + 1 , mid + 1 , e , l , r , v);
fore(i , 2)
tree[i][node] = comb(tree[i][2*node] , tree[i][2*node + 1] , i);
}
int query(int node , int s , int e , int l , int r , int v)
{
if(l <= s && e <= r)
{
return tree[v][node];
}
if(l > e || s > r)
return 0;
propag(node , (e - s + 1)/2);
int mid = (s + e)>>1;
return comb(query(2*node , s , mid , l , r , v) , query(2*node + 1 , mid + 1 , e , l , r , v) , v);
}
int query(int l ,int r ,int v)
{
if(l > r)
return 0;
return query(1 , 0 , BASE - 1 , l , r , v);
}
void upd(int l , int r , int v)
{
if(l > r)
return ;
upd(1 , 0 , BASE - 1 , l , r , v);
}
int n , m;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
vector<vector<int>> queries;
build(n + 1);
fore(i , m)
{
int a , b , c;
cin>>a>>b>>c;
queries.pb({c , a , b});
}
sort(queries.begin() , queries.end());
for(auto Q : queries)
{
int A = Q[1] , B = Q[2] , C = Q[0];
if(A > B)
swap(A , B);
int maxIn = query(A , B - 1 , 1) , maxOut = comb(query(1 , A - 1 , 1) , query(B , n , 1) , 1);
int cte = maxOut - maxIn;
int a = max(0ll , (int)(C - cte)/2);
int b = C - a;
if(a + maxIn == b + maxOut)
{
upd(1 , A - 1 , b);
upd(B , n , b);
upd(A , B - 1 , a);
}
else
{
if(query(A , B - 1 , 0) < query(1 , A - 1 , 0) + query(B , n , 0))
{
if(a < b)
swap(a , b);
}
else if(query(A , B - 1 , 0) > query(1 , A - 1 , 0) + query(B , n , 0))
{
if(a > b)
swap(a , b);
}
else
{
if(b - a > n - (b - a))
{
if(a > b)
swap(a , b);
}
else
{
if(a < b)
swap(a , b);
}
}
upd(1 , A - 1 , b);
upd(B , n , b);
upd(A , B - 1 , a);
}
}
cout<<tree[1][1]<<nl;
}
