// 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.8241271075210637x):
#include<bits/stdc++.h>

#define int ll

using namespace std;typedef long long ll;

#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)

#define RP(t,a,b)  for(register int t=(a),edd=(b);t<=edd;++t)

#define ERP(t,a)   for(register int t=head[a];t;t=e[t].nx)

#define midd register int mid=(l+r)>>1

#define TMP template < class ccf >

#define lef l,mid,pos<<1

#define rgt mid+1,r,pos<<1|1

#define pushup(pos) (seg[pos]=seg[pos<<1]+seg[pos<<1|1])

TMP inline ccf qr(ccf b){

    register char c=getchar();register int q=1;register ccf x=0;

    while(c<48||c>57)q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)x=x*10+c-48,c=getchar();

    return q==-1?-x:x;}

TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}

TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}

TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));}

TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));}

TMP inline ccf READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);}

//----------------------template&IO---------------------------

const int maxn=200005;

struct E{

    int fr,to,w;

    inline bool operator < (E a){return w<a.w;}

}e[maxn<<1];

int cnt;

int r[maxn];

inline void add(int fr,int to,int w){

    e[++cnt]=(E){fr,to,w};

}

inline int q(int x){

    register int t=x,i=x,temp;

    while(r[t]!=t) t=r[t];temp=t;

    while(r[i]!=i) {temp=r[i];r[i]=t;i=temp;}

    return t;    

}



inline bool in(int x,int y){return not(q(x)^q(y));}

inline void j(int x,int y){r[q(x)]=q(y);}



int f[maxn];

int n,m;

signed main(){

    n=qr(1LL);m=qr(1LL);

    RP(t,0,n) r[t]=t;

    register int t1,t2,t3;

    RP(t,0,n+1) f[t]=1LL<<50;

    RP(t,1,m){

	t1=qr(1);

	t2=qr(1);

	t3=qr(1);

	add(t1,t2,t3);

	f[t1]=Min(f[t1],t3+1LL);

	f[t2]=Min(f[t2],t3+2LL);

    }

    RP(t0,1,2) RP(t,0,n) f[t%n]=Min(f[t%n],f[(t-1+n)%n]+2LL);

    RP(t,0,n) add(t%n,(t+1)%n,f[t%n]);

    sort(e+1,e+cnt+1);ll ret=0;

    RP(t,1,cnt){

	if(not in(e[t].fr,e[t].to)){

	    ret+=(ll)e[t].w;

	    j(e[t].fr,e[t].to);

	}

    }

    cout<<ret<<endl;

    return 0;

}