#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define fin "\n"

#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
template <typename T>
inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>
inline void chmax(T &l,T r){l=max(l,r);}

typedef tuple<int,int,int> T;
typedef pair<int,int> P;


namespace _DSU{
#define SZ 212345
    int mem[2][SZ];
}
class UnionFind{
private:
    int *par,*rank;
    int find(int x){
	if (par[x] == x) return x;
	else return par[x] = find(par[x]);
    }
public:
    UnionFind(int n,int *par,int *rank) :par(par),rank(rank){
	for(int i = 0; i < n; i++)par[i] = i,rank[i] = 0;
    }
    UnionFind(int n):UnionFind(n,_DSU::mem[0],_DSU::mem[1]){}
    bool unite(int x, int y){
	x = find(x);y = find(y);
	if (x == y)return false;
	if (rank[x] < rank[y]) par[x] = y;
	else{
	    par[y] = x;
	    if (rank[x] == rank[y])rank[x]++;
	}
	return true;
    }
    bool same(int x, int y){
	return find(x) == find(y);
    }
};

#define fi first
#define se second
int N,Q;

T abc[212345];
vector<P> que[412345];
int main(){
    scanf("%d %d",&N,&Q);
    int LB=1e9;
    REP(i,Q){
        int a,b, c;
        scanf("%d %d %d",&a,&b,&c);
        abc[i]=T(a,b,c);
        chmin(LB,c);
    }
    
    REP(i,Q){
        int a,b,c;
        tie(a,b,c)=abc[i];
        c-=LB;
        if(c<2*N&&a!=b){
            que[c].push_back(P(a,b));
        }
        a=(a+1)%N;
        c++;
        if(c<2*N&&a!=b){
            que[c].push_back(P(a,b));
        }
    }
    UnionFind uf(N);
    LL res=LB*(LL)(N-1);
    
    REP(i,2*N){
        while(!que[i].empty()){
            auto v=que[i].back();que[i].pop_back();
            int a,b;
            tie(a,b)=v;
            int c=i;
            //cout<<a<<b<<c<<endl;
            if(!uf.same(a,b)){
                res+=c;
                uf.unite(a,b);
                que[c+2].push_back(P((a+1)%N,(b+1)%N));
            }
        }
    }
    
    
    
    
    cout<<res<<endl;

    return 0;
}
