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

#define mp make_pair

#define mt make_tuple

#define pb push_back

#define fi first

#define se second

#define sz(a) int(a.size())

#define clr(a) memset(a,0,sizeof(a))

#define all(a) a.begin(),a.end()

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef pair<int,int> pii;

typedef pair<ll,int> pli;

const int inf=1e9;

const ll Inf=1e18;

const int mod=1;

template<typename T=int>

T gi() {

    T x=0,o=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

    if(ch=='-') o=-1,ch=getchar();

    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

    return x*o;

}

template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };

template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };

int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }

int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }

void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }

void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }

string to_string(string s) { return '"'+s+'"'; }

string to_string(const char *s) { return to_string((string)s); }

string to_string(bool b) { return (b?"true":"false"); }

template<typename A,typename B> string to_string(pair<A,B> p) {

    return "("+to_string(p.fi)+","+to_string(p.se)+")";

}

template<typename T> string to_string(T v) {

    int fst=1;string ret="{";

    for(auto x:v) {

        if(!fst) ret+=",";

        fst=0,ret+=to_string(x);

    }

    ret+="}";return ret;

}

void dbg_out() { cerr<<endl; }

template<typename Head,typename... Tail> void dbg_out(Head H,Tail... T) {

    cerr<<" "<<to_string(H);

    dbg_out(T...);

}

#define dbg(...) cerr<<"{"<<#__VA_ARGS__<<"}:",dbg_out(__VA_ARGS__)



template<typename T>

int qpow(int a,T b) {

    int ret=1;

    while(b) {

        if(b&1) ret=1ll*ret*a%mod;

        a=1ll*a*a%mod,b>>=1;

    }

    return ret;

}



const int N=2e5+10;



int n,Q,f[N];

vector<tuple<int,int,int>> e;



namespace dsu {



    int fa[N];



    void init() {

        for(int i=1;i<=n;i++) fa[i]=i;

    }



    int getf(int x) {

        return x==fa[x]?x:fa[x]=getf(fa[x]);

    }



    bool merge(int x,int y) {

        x=getf(x),y=getf(y);

        if(x==y) return 0;

        fa[y]=x;return 1;

    }

    

}



int main() {

    n=gi(),Q=gi();

    memset(f,0x3f,sizeof(f));

    while(Q--) {

        int a=gi()+1,b=gi()+1,c=gi();

        chkmin(f[a],c+1),chkmin(f[b],c+2);

        e.pb(mt(c,a,b));

    }

    for(int i=2;i<=n;i++) chkmin(f[i],f[i-1]+2);

    chkmin(f[1],f[n]+2);

    for(int i=2;i<=n;i++) chkmin(f[i],f[i-1]+2);

    for(int i=1;i<=n;i++) e.pb(mt(f[i],i,i%n+1));

    dsu::init();

    sort(all(e));

    ll ans=0;

    for(auto x:e) {

        int u=get<1>(x),v=get<2>(x),w=get<0>(x);

        if(dsu::merge(u,v)) ans+=w;

    }

    printf("%lld\n",ans);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.820543554649317x):
#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.