#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200005;
const ll INF = ll(1e18);
struct E{ int s, e; ll x; };
int n, q, c, p[N];
ll v[N], w[N], r;
E e[2 * N];
int f(int x){ return p[x] = (x == p[x] ? x : f(p[x])); }
int main(){
scanf("%d%d", &n, &q);
fill(v, v + n, INF);
fill(w, w + n, INF);
for(int x, y, z; q--; ){
scanf("%d%d%d", &x, &y, &z);
v[x] = min(v[x], z + 1LL);
v[y] = min(v[y], z + 2LL);
e[c++] = {x, y, ll(z)};
}
ll m = INF;
for(int i = 0; i < 2 * n; i++){
m = min(m + 2, v[i % n]);
w[i % n] = min(w[i % n], m);
}
for(int i = 0; i < n; i++) e[c++] = {i, (i + 1) % n, w[i]};
sort(e, e + c, [](E x, E y){ return x.x < y.x; });
iota(p, p + n, 0);
for(int i = 0; i < c; i++){
int x = f(e[i].s), y = f(e[i].e);
if(x == y) continue;
r += e[i].x;
p[y] = x;
}
printf("%lld\n", r);
}