// Slower C++ solution:
// #define FNAME "template"



#include <bits/stdc++.h>

using namespace std;



typedef long long inte;

const int maxn = 200005;



#ifndef NDEBUG

#    define dprint(x) (cerr << (#x) << " = "<< (x) << endl)

#else

#    define dprint(x) (NULL)

#endif



template<typename T>

inline void readFig(T& x)

{

#   ifdef FTREAD

        static int c = 0;

        int op = 1;

        x = 0;

        while (!isdigit(c)) {

            if (c == '-')

                op = -1;

            c = getchar();

        }

        while (isdigit(c)) {

            x *= 10;

            x += c - '0';

            c = getchar();

        }

        x *= op;

#   else

        cin >> x;

#   endif

}



struct Edge {

    int u, v;

    inte w;

} edges[maxn * 2];



bool operator <(const Edge& a, const Edge& b)

{

    return a.w < b.w;

}



inte tra[maxn];



int par[maxn];

int getPar(int x)

{

    if (par[x] == x)

        return x;

    else 

        return par[x] = getPar(par[x]);

}



inline void solve()

{

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

    int N, Q;

    readFig(N); readFig(Q);

    for (int i = 1; i <= N; ++i)

        par[i] = i;

    for (int i = 1; i <= Q; ++i) {

        inte A, B, C;

        readFig(A); readFig(B); readFig(C);

        edges[i].u = A;

        edges[i].v = B;

        edges[i].w = C;

        tra[A] = min(tra[A], C + 1);

        tra[B] = min(tra[B], C + 2);

    }

    for (int i = 0; i < N * 2; ++i)

        tra[(i + 1) % N] = min(tra[(i + 1) % N], tra[i % N] + 2);

    for (int i = 0; i < N; ++i) {

        const int p = i + Q + 1;

        edges[p].u = i;

        edges[p].v = (i + 1) % N;

        edges[p].w = tra[i];

    }

    const int tot = N + Q;

    sort(edges + 1, edges + tot + 1);

    inte ans = 0;

    int cnt = 0;

    for (int i = 1; i <= tot; ++i) {

        if (getPar(edges[i].u) != getPar(edges[i].v)) {

            par[getPar(edges[i].u)] = getPar(edges[i].v);

            ans += edges[i].w;

            ++cnt;

        }

    }

    assert(cnt == N - 1);

    cout << ans << endl;

}



signed main()

{

#   ifdef FNAME

        freopen(FNAME".in", "r", stdin);

        freopen(FNAME".out", "w", stdout);

#   endif

#   ifndef FTREAD

    	ios::sync_with_stdio(false);

    	cin.tie(0);

#   endif



#   ifdef MULTEST

        int T;

        readFig(T);

        while (T--)

            solve();

#   else

        solve();

#   endif



#   ifdef FNAME

        fclose(stdin);

        fclose(stdout);

#   endif

    	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 2.6671506248549743x):
#include<bits/stdc++.h>

#define maxn 800010

#define inf 2000000000

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,q,tot,cnt;

ll ans;

int fa[maxn],t[maxn];

struct edge

{

    int x,y;

    ll v;

}e[maxn];

bool cmp(const edge &a,const edge &b)

{

    return a.v<b.v;

}

int find(int x)

{

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

}

int main()

{

    read(n),read(q),cnt=n-1;

    for(int i=0;i<n;++i) fa[i]=i,t[i]=inf;

    for(int i=1;i<=q;++i)

    {

        int x,y,v;

        read(x),read(y),read(v);

        e[++tot]={x,y,v},t[x]=min(t[x],v+1),t[y]=min(t[y],v+2);

    }

    for(int i=0;i<=2*n;++i) t[i%n]=min(t[i%n],t[(i-1+n)%n]+2);

    for(int i=0;i<n;++i) e[++tot]={i,(i+1)%n,t[i]};

    sort(e+1,e+tot+1,cmp);

    for(int i=1;i<=tot;++i)

    {

        int x=find(e[i].x),y=find(e[i].y);

        if(x==y) continue;

        fa[x]=y,ans+=e[i].v;

        if(++cnt==n-1) break;

    }

    printf("%lld",ans);

    return 0;

}