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

#define int long long

#define rg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

using namespace std;

const int mod=1e9+7;

int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

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

    return f*x;

}

struct node {

	int x,y,z;

}a[1000001];

int val[1000001],pre[1000001],x,y,z,cnt,js,ans;

int find(int x){

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

}

bool cmp(const node & a , const node & b ){

	return a.z<b.z;

}

main(){

	int n=read(),m=read();

	memset(val,127/3,sizeof(val));

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

		x=read()+1,y=read()+1,z=read(),cnt++;

		a[cnt].x=x,a[cnt].y=y,a[cnt].z=z;

		val[x]=min(val[x],z+1);

		val[y]=min(val[y],z+2);

	}

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

		val[i]=min(val[i],val[i-1]+2);

	val[1]=min(val[1],val[n]+2);

	for(int i=2;i<=n;i++)

		val[i]=min(val[i],val[i-1]+2);

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

		cnt++,a[cnt].x=i,a[cnt].y=i%n+1,a[cnt].z=val[i],pre[i]=i;

	sort(a+1,a+1+cnt,cmp);

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

		int fx=find(a[i].x),fy=find(a[i].y);

		if(fx!=fy)

			js++,ans+=a[i].z,pre[fx]=fy;

		if(js==n-1) printf("%lld",ans),exit(0);

	}

}

// Faster C++ solution for the same problem (measured speedup: 3.6260189110635x):
/*

 　　　　　／＞　 フ

 　　　　　| 　_　 _|

 　 　　　／`ミ _x 彡

 　　 　 /　　　 　 |

 　　　 /　  ヽ　　 ?

 　／￣|　　 |　|　|

 　| (￣ヽ＿_ヽ_)_)

 　＼二つ

  */



#include <queue>

#include <vector>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define MP make_pair

#define ll long long

#define fi first

#define se second

using namespace std;



template <typename T>

void read(T &x) {

    x = 0; bool f = 0;

    char c = getchar();

    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;

    for (;isdigit(c);c=getchar()) x=x*10+(c^48);

    if (f) x=-x;

}



template<typename F>

inline void write(F x, char ed = '\n') {

    static short st[30];short tp=0;

    if(x<0) putchar('-'),x=-x;

    do st[++tp]=x%10,x/=10; while(x);

    while(tp) putchar('0'|st[tp--]);

    putchar(ed);

}



template <typename T>

inline void Mx(T &x, T y) { x < y && (x = y); }



template <typename T>

inline void Mn(T &x, T y) { x > y && (x = y); }



const int N = 400005;

struct edges {

    int x, y, val;

    bool operator < (const edges &i) const {

        return val < i.val;

    }

}ed[N];



int d[N], f[N], cnt, m, n; ll ans;

int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

int main() {

    read(n), read(m);

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

    for (int i = 1, x, y, z;i <= m; i++) {

        read(x), read(y), read(z);

        ed[++cnt] = (edges){x, y, z};

        Mn(d[x], z + 1), Mn(d[y], z + 2);

    }

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

        Mn(d[i], d[i-1] + 2);

    Mn(d[0], d[n]);

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

        Mn(d[i], d[i-1] + 2);

    Mn(d[0], d[n]);

    for (int i = 0;i < n; i++)

        ed[++cnt] = (edges){i, (i + 1) % n, d[i]};

    sort(ed + 1, ed + cnt + 1);

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

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

        int x = ed[i].x, y = ed[i].y, z = ed[i].val;

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

        x != y && (ans += z, f[x] = y);

    }

    write(ans);

    return 0;

}