#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int head[N],cnt; //----------------------------------------------------------------------Graph
struct edge
{
    int x,y,dis;
    bool operator < (const edge a)const
    {
        return dis<a.dis;
    }
}e[N<<3];
int n,m,k;long long ans;
int a[N];
int fa[N];
int gf(int k)
{
    return fa[k]==k?k:fa[k]=gf(fa[k]);
}
int main()
{
    int u,v,w;
    scanf("%d%d",&n,&m);
    memset(a,127,sizeof(a));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].dis);
        a[e[i].x]=min(e[i].dis+1,a[e[i].x]);
        a[e[i].y]=min(e[i].dis+2,a[e[i].y]);
    }
    cnt=m;
    int s=2000000000;
    for(int i=0;i<2*n;i++)
    {
        s=min(s+2,a[i%n]);
        if(i>=n)
            e[++cnt].x=i%n,e[cnt].y=(i+1)%n,e[cnt].dis=s;
    }
    sort(e+1,e+cnt+1);
    for(int i=0;i<n;i++)
        fa[i]=i;
    for(int i=1;i<=cnt;i++)
    {
        u=e[i].x,v=e[i].y;
        if(gf(u)==gf(v))continue;
        ans+=e[i].dis;
        fa[gf(u)]=gf(v);
    }
    printf("%lld",ans);
    return 0;
}
