#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=200005;
ll n,m,q,x[N],f[N],ans,que[N],h,t=1,in[N];
struct edge{
	ll s,t,v;
};
bool cmp(edge a,edge b){
	return a.v<b.v;
}
ll find(ll v){
	if(!(~f[v]))return v;
	return f[v]=find(f[v]);
}
edge e[N<<1];
int main(){
	scanf("%lld%lld",&n,&q);
	for(ll i=0;i<n;i++)x[i]=1ll<<60,f[i]=-1;
	while(q--){
		ll a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		e[m++]=(edge){a,b,c};
		x[a]=min(x[a],c+1);
		x[b]=min(x[b],c+2);
	}
	for(ll i=0;i<n;i++)in[que[++h]=i]=1;//,printf("in %lld\n",i);
	//for(ll i=0;i<n;i++)printf("%lld ",x[i]);printf("\n");
	while(t<=h){
		ll v=que[(t++)%N];
		in[v]=0;
		if(x[v]+2<x[(v+1)%n]){
			x[(v+1)%n]=x[v]+2;//printf("x[%lld]=%lld\n",(v+1)%n,x[v]+2);
			if(!in[(v+1)%n])que[(++h)%N]=(v+1)%n,in[(v+1)%n]=1;//printf("in %lld\n",(v+1)%n);
		}
	}
	for(ll i=0;i<n;i++)e[m++]=(edge){i,(i+1)%n,x[i]};
	sort(e,e+m,cmp);//printf("============\n");
	//for(ll i=0;i<m;i++)printf("%lld %lld %lld\n",e[i].s,e[i].t,e[i].v);
	for(ll i=0,j=0;j<n-1;i++){
		ll v=find(e[i].s),u=find(e[i].t);
		if(v!=u)j++,f[v]=u,ans+=e[i].v;
	}
	printf("%lld\n",ans);
	return 0;
}