#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
//#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}
ll MOD=998244353;
#define N 11000000

ll int inv[N],comb[N],prd[N],invprd[N];
void calc_inv(){
    inv[1]=1;
    rep2(i,2,N-1){
        inv[i]=((-(MOD/i)*inv[MOD%i])%MOD+MOD)%MOD;
    }
    return;
}
void calc_comb(ll int n){
    comb[0]=1;
    rep2(i,1,n){
        comb[i]=comb[i-1]*(n+1-i)*inv[i]%MOD;
    }
    return;
}
void calc_product(){
    prd[0]=prd[1]=1;
    invprd[0]=invprd[1]=1;
    rep2(i,2,N-1){
        prd[i]=i*prd[i-1]%MOD;
        invprd[i]=inv[i]*invprd[i-1]%MOD;
    }
    return ;
}
ll cmb(int a,int b){
    if(a<b)return 0;
    if(a<0||b<0)return 0;
    return prd[a]*invprd[b]%MOD*invprd[a-b]%MOD;
}
ll modpow(ll x,ll n){
    if(n==0) return 1;
    ll res=modpow(x*x%MOD,n/2);
    if(n&1) res=res*x%MOD;
    return res;
}
ll p[N+100],a[N],b[N];

struct UnionFind {
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }
};

struct querry{
  int a,b;
  ll c;
  int ato;
  bool operator<(const querry &x) const{
  return c<x.c;};
};
main(){
  int n,q;
  cin>>n>>q;
  priority_queue<querry> pq;
  UnionFind uf(n);
  ll ans=0;
  rep(i,q){
    int a,b,c;
    cin>>a>>b>>c;
    pq.emplace(querry{a,b,-c,1});
  }
  
  while(!pq.empty()){
    querry now=pq.top();
    pq.pop();
    //cout<<now.a<<now.b<<now.c<<now.ato<<endl;
    //continue;
    if(!uf.unite(now.a,now.b)){
      swap(now.a,now.b);
      now.b++;now.c--;
      if(now.b>=n) now.b-=n;
      if(now.ato){now.ato=0;pq.emplace(now);}
    }
    else{
      //cout<<now.a<<now.b<<endl;
      now.a++;
      if(now.a>=n)now.a-=n;
      swap(now.a,now.b);
      now.ato=1;
      ans+=now.c;
      now.c--;
      pq.emplace(now);
      if(uf.size(now.a)==n){
      cout<<-ans;return 0;}
    }
  }
}


Measured memory_bytes: 9328