#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct edge{
	int x,y;
	ll z;
} gs[400400];
int n,m;
ll ans;
ll best[200200];

int p[200200];
int par(int x){
	return (p[x]==x)?x:(p[x]=par(p[x]));
}

int main(){
	scanf("%d%d",&n,&m);
	memset(best,0x7f,sizeof best);
	for (int i=0;i<n;++i)
		p[i]=i;

	for (int i=0;i<m;++i){
		static int x,y;
		static ll z;
		scanf("%d%d%lld",&x,&y,&z);
		gs[i]=(edge){x,y,z};
		best[x]=min(best[x],z+1);
		best[y]=min(best[y],z+2);
	}

	for (int it=0;it<2;++it)
		for (int i=0;i<n;++i)
			best[(i+1)%n]=min(best[(i+1)%n],best[i]+2);

	for (int i=0;i<n;++i)
		gs[m+i]=(edge){i,(i+1)%n,best[i]};

	sort(gs,gs+m+n,[](const edge &a,const edge &b){return a.z<b.z;});
	for (int i=0;i<m+n;++i){
		int fa=par(gs[i].x);
		int fb=par(gs[i].y);
		if (fa!=fb){
			ans+=gs[i].z;
			p[fa]=fb;
		}
	}
	printf("%lld\n", ans);
}