#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);
}