// Slower C++ solution:
#include<algorithm>

#include<cstdio>

#include<cstring>

#define N 500000

#define NN 200005

using namespace std;

struct ahh{

	int u,v,next;

	long long w;

}a[N];

int fa[NN],head[NN],n,m,tot,x,y;

long long sum,best[NN],v;

void add(int u,int v,long long w){

	tot++;

	a[tot].u=u;a[tot].v=v;a[tot].w=w;

}

bool cmp(ahh x,ahh y){return (x.w<y.w);}

int find(int x){

	if (fa[x]!=x)fa[x]=find(fa[x]);

	return fa[x];

}

void Union(int x,int y){

	int x1=find(x);

	int y1=find(y);

	if (x1!=y1)fa[y1]=x1;

}

void kruskal(){

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

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

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

		if (find(a[i].u)!=find(a[i].v))Union(a[i].u,a[i].v),sum+=a[i].w;

}

int main(){

//	freopen("L.in","r",stdin);

	tot=0;

	sum=0;

	memset(best,127,sizeof(best));

	scanf("%d%d",&n,&m);

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

		scanf("%d%d%lld",&x,&y,&v);

		add(x,y,v);

		best[x%n]=min(best[x%n],v+1);

		best[y%n]=min(best[y%n],v+2);

	}

	for (int t=0;t<2;t++)

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

			best[(i+1)%n]=min(best[(i+1)%n],best[i]+2);

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

		add(i,(i+1)%n,best[i]);

	}

	kruskal();

	printf("%lld",sum);

}


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

#include <algorithm>

#include <bitset>

#include <cassert>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <fstream>

#include <functional>

#include <iomanip>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <string>

// #include <unordered_map>

// #include <unordered_set>

#include <utility>

#include <vector>



#define pb push_back

#define mp make_pair

#define sqr(x) ((x) * (x))



#ifdef ONLINE_JUDGE

#define link renamelink

#define next renamenext

#define prev renameprev

#endif



using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

typedef long double ld;



// #define ONLINE_JUDGE

inline void EnableFileIO(const string& fileName) {

  if (fileName.empty()) return;

#ifdef ONLINE_JUDGE

  freopen((fileName + ".in").c_str(), "r", stdin);

  freopen((fileName + ".out").c_str(), "w", stdout);

#endif

}



const int INF = (1 << 30) - 1;

const LL LINF = (1LL << 61) - 1;

const double EPS = 1e-10, PI = acos(-1);

const int N = 2e5 + 100;



int n, q;

typedef pair<LL, pii> tup;

priority_queue<tup, vector<tup>, greater<tup> > pq;

vector<tup> es;



LL nxt[N];

int fa[N];



int getfa(int k) { return fa[k] == k ? k : fa[k] = getfa(fa[k]); }



int main() {

  // srand((int)time(0));

  // printf("Hello, world!\n");

  // EnableFileIO("");

  ios::sync_with_stdio(false);

  cin.tie(0);



  scanf("%d%d", &n, &q);

  for (int i = 0; i < n; i++) nxt[i] = LINF, fa[i] = i;

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

    int u, v;

    LL k;

    scanf("%d%d%lld", &u, &v, &k);

    es.pb(mp(k, mp(u, v)));

    nxt[u] = min(nxt[u], k + 1);

    nxt[v] = min(nxt[v], k + 2);

  }

  for (int i = 0; i < n * 3; i++) {

    nxt[(i + 1) % n] = min(nxt[(i + 1) % n], nxt[i % n] + 2);

  }

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

    es.pb(mp(nxt[i], mp(i, (i + 1) % n)));

    // cerr << i << ' ' << nxt[i] << endl;

  }

  sort(es.begin(), es.end());



  LL ans = 0;

  for (int i = 0; i < es.size(); i++) {

    LL k = es[i].first;

    int u = es[i].second.first, v = es[i].second.second;



    if (getfa(u) == getfa(v)) continue;

    // cerr << k << ' ' << u << ' ' << v << endl;

    ans += k;

    fa[getfa(u)] = getfa(v);

  }

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

  return 0;

}