#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;
typedef long long lo;
template<typename tp> inline void read(tp &x) {
x = 0; char c = getchar(); int f = 0;
for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
if (f) x = -x;
}
#define int long long
const int N = 1e6 + 233;
const int M = N * 4;
struct E {
int from, to, w;
}e[M]; int e_cnt = 0;
int n, q, inf, pre[N], suf[N];
inline void link(int x, int y, int w) {
if (w == inf) return ;
// cout << x - 1 << " " << y - 1 << " " << w << "\n";
e[++e_cnt] = (E) {x, y, w};
}
namespace dsu {
int pre[N];
inline int find(int x) {
return pre[x] == x ? x : pre[x] = find(pre[x]);
}
inline void init(int n) {
rep (i, n) pre[i] = i;
}
inline void make(int x, int y) {
pre[find(x)] = find(y);
}
}
inline void doit() {
sort(e + 1, e + e_cnt + 1, [](E a, E b) {
return a.w < b.w;
});
dsu::init(n);
int ans = 0;
rep (i, e_cnt) {
int fx = dsu::find(e[i].from);
int fy = dsu::find(e[i].to);
if (fx != fy) {
ans += e[i].w;
dsu::make(fx, fy);
}
}
cout << ans << "\n";
}
signed main(void) {
read(n); read(q);
memset(pre, 38, sizeof pre);
memset(suf, 38, sizeof suf);
inf = pre[0];
rep (i, q) {
int x, y, w; read(x); read(y); read(w);
++x; ++y;
link(x, y, w);
// if (x < y) {
pre[x] = min(pre[x], w + 1);
pre[y] = min(pre[y], w + 2);
// } else {
// pre[x] = min(pre[x], w + 2);
// pre[y] = min(pre[y], w + 1);
// }
}
for (int i = 1; i <= n + n; i++) {
pre[i] = min(pre[i], pre[i - 1] + 2);
}
// for (int i = n + n; i >= 1; i--) {
// suf[i] = min(suf[i], suf[i + 1] + 2);
// }
// for (int i = 1; i <= n + n; i++)
// cout << pre[i] << " \n"[i == n + n];
for (int i = 1; i <= n + n - 1; i++) {
int x = i, y = i + 1;
if (x > n) x -= n;
if (y > n) y -= n;
link(x, y, pre[i]);
// link(x, y, suf[i + 1]);
}
doit();
}