// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

const ll MAXN=4e5+51;

struct Edge{

	ll from,to,dist;

	inline bool operator <(const Edge &rhs)const

	{

		return this->dist<rhs.dist;

	}

};

Edge ed[MAXN];

ll nc,cnt,x,y,z,tot;

ll dist[MAXN],boss[MAXN];

inline ll read()

{

    register ll num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

} 

inline void setup(ll cnt)

{

	for(register int i=0;i<cnt;i++)

	{

		boss[i]=i;

	}

}

inline void update()

{

	for(register int i=0;i<nc;i++)

	{

		dist[i]=min(dist[i],dist[(i+nc-1)%nc]+2);

	}

}

inline ll findb(ll node)

{

	if(node==boss[node])

	{

		return node;

	}

	boss[node]=findb(boss[node]);

	return boss[node];

}

inline void Union(ll x,ll y)

{

	ll bx=findb(x),by=findb(y);

	if(bx!=by)

	{

		boss[by]=bx;

	}

}

inline ll Kruskal()

{

	ll res=0,k=0;

	sort(ed,ed+tot),setup(nc);

	for(register int i=0;k<nc-1;i++)

	{

		if(findb(ed[i].from)!=findb(ed[i].to))

		{

			Union(ed[i].from,ed[i].to),res+=ed[i].dist,k++;

		}

	}

	return res;

}

int main()

{

	nc=read(),cnt=read(),memset(dist,0x3f,sizeof(dist));

	for(register int i=0;i<cnt;i++)

	{

		x=read(),y=read(),z=read();

		ed[tot++]=(Edge){x,y,z};

		dist[x]=min(dist[x],z+1),dist[y]=min(dist[y],z+2);

	}

	update(),update();

	for(register int i=0;i<=nc;i++)

	{

		ed[tot++]=(Edge){i,(i+1)%nc,dist[i]};

	}

	printf("%lld",Kruskal());

}

// Faster C++ solution for the same problem (measured speedup: 4.237108965754606x):
#pragma GCC optimize(2,3,"Ofast")

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define re register int

#define db double

#define in inline

namespace fast_io

{

	char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny;

	in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}

	in int read()

	{

		re x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;Bi=1;if(nc<0)return nc;

		x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*ny;

	}

	in db gf() {re a=read(),y=ny,b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi)*y:a);}

	in int gs(char *s) {char c,*t=s;while(c=gc(),c<32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}

	in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}

	in void flush() {if(C>1<<22) ot();}

	template <typename T>

	in void write(T x,char t)

	{

		re y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);

		if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();

	}

	in void write(char *s) {re l=strlen(s);for(re i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}

};

using namespace fast_io;

#define pb push_back

const int N=2e5+5;

int n,m,d[N],fa[N],tot;ll ans;

struct did{int u,v;ll w;in bool operator<(did a)const{return w<a.w;}}e[N<<3];

int getfa(re x) {return fa[x]^x?fa[x]=getfa(fa[x]):x;}

in int merge(re x,re y)

{

	re u=getfa(x),v=getfa(y);

	return u^v?fa[u]=v,1:0;

}

int main()

{

	n=read(),m=read();memset(d+1,63,4*n);

	for(re i=1,u,v,w;i<=m;i++)

	{

		u=read()+1,v=read()+1,w=read();e[++tot]={u,v,w};

		d[u]=min(d[u],w+1);d[v]=min(d[v],w+2);

	}

	for(re i=1;i<=n;i++) d[i%n+1]=min(d[i%n+1],d[i]+2);

	for(re i=1;i<=n;i++) d[i%n+1]=min(d[i%n+1],d[i]+2);

	for(re i=1;i<=n;i++) e[++tot]={i,i%n+1,d[i]},fa[i]=i;

	sort(e+1,e+tot+1,[](did a,did b){return a.w<b.w;});

	for(re i=1,cnt=n;i<=tot&&cnt>1;i++) if(merge(e[i].u,e[i].v)) cnt--,ans+=e[i].w;

	write(ans,'\n');

	return ot(),0;

}

//Author: disangan233

//In my dream's scene,I can see the everything that in Cyaegha.