#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using uint=unsigned int;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

ll readLL(){
	ll i;
	scanf("%lld",&i);
	return i;
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

struct UnionFind{
	vi rank,par;
	void Init(int n){
		rank.assign(n,0);
		par.assign(n,-1);
	}
	int Find(int i){
		return par[i]==-1?i:(par[i]=Find(par[i]));
	}
	bool Same(int a,int b){
		return Find(a)==Find(b);
	}
	bool Unite(int a,int b){
		a=Find(a);
		b=Find(b);
		if(a==b)
			return false;
		if(rank[a]<rank[b])
			swap(a,b);
		par[b]=a;
		if(rank[a]==rank[b])
			rank[a]++;
		return true;
	}
} uf;

int main(){
	int n=read(),q=read();
	map<int,vector<pii>> edges;
	int minCost=INT_MAX;
	REP(_,q){
		int a=read(),b=read(),c=read();
		chmin(minCost,c);
		edges[c].PB(MP(a,b));
		edges[c+1].PB(MP((a+1)%n,b));
	}
	int curCost=minCost,cmp=n;
	uf.Init(n);
	ll ans=0;
	while(cmp>1){
		for(auto e:edges[curCost])
			if(!uf.Same(e.first,e.second)){
				cmp--;
				ans+=curCost;
				uf.Unite(e.first,e.second);
				edges[curCost+2].PB(MP((e.first+1)%n,(e.second+1)%n));
			}
		curCost++;
	}
	cout<<ans<<endl;
}
