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

#define dd ch=getchar()
inline int read()
{
	int x=0;char dd;bool f=false;
	while(!isdigit(ch))f|=ch=='-',dd;
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,dd;
	return f?-x:x;
}
#undef dd
void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
#define writesp(x) (write(x),putchar(' '))
#define writeln(x) (write(x),putchar('\n'))

const int N=2e5+5;

int n,m;
int minn[N],fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline int pos(int x){return (x-1)%n+1;}
struct node{int u,v,w;}a[N<<1];
int tot=0;
inline void add(int u,int v,int w){a[++tot]=(node){u,v,w};}
inline bool cmp(const node &x,const node &y){return x.w<y.w;}
inline void CLANNAD_TXDY()
{
	sort(a+1,a+1+tot,cmp);
	for(int i=1;i<=n;i++)fa[i]=i;
	int cnt=0,ans=0;
	for(int i=1;i<=tot;i++)
	{
		int x=a[i].u,y=a[i].v,w=a[i].w;
		if(find(x)==find(y))continue;
		fa[find(x)]=find(y);
		ans+=w;
		if(++cnt==n-1)break;
	}
	writeln(ans);
}
signed main()
{
	n=read(),m=read();
	memset(minn,0x3f,sizeof(minn));
	for(int i=1;i<=m;i++)
	{
		int u=read()+1,v=read()+1,w=read();
		minn[u]=min(minn[u],w+1);
		minn[v]=min(minn[v],w+2);
		add(u,v,w);
	}
	for(int i=1;i<=n;i++)
		minn[pos(i+1)]=min(minn[pos(i+1)],minn[i]+2);
	for(int i=1;i<=n;i++)
		minn[pos(i+1)]=min(minn[pos(i+1)],minn[i]+2);
	for(int i=1;i<=n;i++)
		add(i,pos(i+1),minn[i]);
	CLANNAD_TXDY();
	return 0;
}