#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005;
struct node
{
	int x,y,z;
}e[N*2];
int n,q,i,j,k,w[N],cnt,p[N];
long long ans;
bool cmp(node a,node b)
{
	return a.z<b.z;
}
int find(int x)
{
	return p[x]==-1?x:p[x]=find(p[x]);
}
int main()
{
	scanf("%d%d",&n,&q);
	for(i=0;i<n;++i)
		p[i]=-1;
	for(i=0;i<n;++i)
		w[i]=1<<30;
	for(i=1;i<=q;++i)
	{
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
		w[e[i].x]=min(w[e[i].x],e[i].z+1);
		w[e[i].y]=min(w[e[i].y],e[i].z+2);
	}
	for(i=1;i<n;++i)
		w[i]=min(w[i],w[i-1]+2);
	w[0]=min(w[0],w[n-1]+2);
	for(i=1;i<n;++i)
		w[i]=min(w[i],w[i-1]+2);
	cnt=q;
	for(i=0;i<n-1;++i)
		e[++cnt]=(node){i,i+1,w[i]};
	e[++cnt]=(node){n-1,0,w[n-1]};
	sort(e+1,e+1+cnt,cmp);
	for(i=1;i<=cnt;++i)
		if(find(e[i].x)!=find(e[i].y))
		{
			p[find(e[i].x)]=find(e[i].y);
			ans+=e[i].z;
		}
	printf("%lld",ans);
	return 0;
}
