#include<bits/stdc++.h>
namespace IO{
	const int maxn(1<<21|1);
	char ibuf[maxn],*iS,*iT,obuf[maxn],*oS=obuf,*oT=obuf+maxn-1,_c,_st[55];
	int _f,tp;
	char Getc(){return (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,maxn,stdin),(iS==iT?EOF:*iS++)):*iS++);}
	void Flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
	void Putc(char x){*oS++=x;if(oS==oT)Flush();}
	template<class Int>void Input(Int &x){
		for(_f=0,_c=Getc();_c<'0'||_c>'9';_c=Getc())_f=_c=='-';
		for(x=0;_c<='9'&&_c>='0';_c=Getc())x=(x<<3)+(x<<1)+(_c^48);
		if(_f)x=-x;
	}
	template<class Int>void Print(Int x){
		if(!x)Putc('0');
		if(x<0)Putc('-'),x=-x;
		while(x)_st[++tp]=x%10+'0',x/=10;
		while(tp)Putc(_st[tp--]);
	}
}
using namespace IO;
using namespace std;
const int _=1e6+5;
int f[_],A[_],B[_],W[_],fa[_],n,m;
int cmp(int x,int y){return W[x]<W[y];}
vector<int>fz;int x,y=2e9;
int fi(int x){return fa[x]?fa[x]=fi(fa[x]):x;}
int main(){
	Input(n);Input(m);memset(f,63,sizeof(f));
	for(int i=1;i<=m;++i){
		Input(A[i]);Input(B[i]);Input(W[i]);++A[i];++B[i];
		f[A[i]]=min(f[A[i]],W[i]+1);f[B[i]]=min(f[B[i]],W[i]+2);
		if(f[A[i]]<y)x=A[i],y=f[x];
		if(f[B[i]]<y)x=B[i],y=f[x];
	}
	for(int i=x;i<=n;++i)f[i]=min(f[i],f[i-1]+2);f[1]=min(f[1],f[n]+2);
	for(int i=2;i<=x;++i)f[i]=min(f[i],f[i-1]+2);
	for(int i=1;i<=n;++i)A[++m]=i,B[m]=i%n+1,W[m]=f[i];
	for(int i=1;i<=m;++i)fz.push_back(i);
	sort(fz.begin(),fz.end(),cmp);
	long long ans=0;
	for(int i:fz){
		int fx=fi(A[i]),fy=fi(B[i]);
		if(fx!=fy)fa[fx]=fy,ans+=W[i];
	}
	cout<<ans<<endl;
}
