#include<bits/stdc++.h>
#define int long long
#define LL long long
#define RG register
using namespace std;
template<class T> inline void read(T &x) {
x = 0; RG char c = getchar(); bool f = 0;
while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
x = f ? -x : x;
return ;
}
template<class T> inline void write(T x) {
if (!x) {putchar(48);return ;}
if (x < 0) x = -x, putchar('-');
int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N = 200010;
struct Edge {
int u, v, w;
bool operator < (const Edge &z) const {
return w < z.w;
}
}e[N << 1];
int n, q, c, w[N], fa[N];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
read(n), read(q);
int tot = 0;
memset(w, 127, sizeof(w));
for (int i = 1, x, y, z; i <= q; i++) {
read(x), read(y), read(z);
e[++tot] = (Edge) {x, y, z};
w[x] = min(w[x], z + 1); w[y] = min(w[y], z + 2);
}
for (int i = 0; i < n; i++) w[i] = min(w[i], w[(i - 1 + n) % n] + 2);
for (int i = 0; i < n; i++) w[i] = min(w[i], w[(i - 1 + n) % n] + 2);
for (int i = 0; i < n; i++) e[++tot] = (Edge) {i, (i + 1) % n, w[i]};
sort(e + 1, e + 1 + tot);
for (int i = 0; i < n; i++) fa[i] = i;
int ans = 0;
for (int i = 1; i <= tot; i++) {
int u = find(e[i].u), v = find(e[i].v);
if (u == v) continue;
ans += e[i].w;
fa[v] = u;
}
printf("%lld\n", ans);
return 0;
}