#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define re register
#define gc getchar()
int read()
{
	re int x(0),f(1);re char ch(gc);
	while(ch>'9'||ch<'0') {if(ch=='-')f=-1;ch=gc;}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc;
	return x*f;
}

const int N=2e5+10;

int n,q,m;

struct line {int u,v,w;}e[N<<1];
bool operator < (line a,line b){return a.w<b.w;}
int f[N],v[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
ll ans;

int main()
{
    n=read(),q=read();
    memset(v,127,sizeof(v));
    while(q--)
    {
        int a=read()+1,b=read()+1,c=read();
        e[++m]=(line){a,b,c};
        v[a%n+1]=min(v[a%n+1],c+1);
        v[b%n+1]=min(v[b%n+1],c+2);
    }
    int pos(1);
    for(int i=2;i<=n;++i)
        if(v[i]<v[pos])
            pos=i;
    for(int i=pos%n+1,j=pos;i!=pos;j=i,i=i%n+1)
        v[i]=min(v[i],v[j]+2);
    for(int i=2;i<=n;++i)
        e[++m]=(line){i-1,i,v[i]};
    e[++m]=(line){1,n,v[1]};
    sort(e+1,e+1+m);
    for(int i=1;i<=n;++i)
        f[i]=i;
    for(int i=1;i<=m;++i)
    {
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        ans+=e[i].w;f[u]=v;
    }
    cout<<ans<<'\n';
    return 0;
}