#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
struct lpl{
    int a, b; long long len;
    inline bool operator < (const lpl &A)const{
        return (len == A.len) ? ((a == A.a) ? (b > A.b) : (a > A.a)) : (len > A.len);
    }
};
int n, Q;
bool f[N];
vector<lpl> edge;
priority_queue<lpl> q;

inline int nxt(int t){return (t % n + 1);}

namespace MST{
    int fa[N];

    int find(int t){return (t == fa[t]) ? t : (fa[t] = find(fa[t]));}

    inline long long kruscal(){
        int tot = 0, A = 0, B = 0; long long ret = 0;
        //printf("\n");
        sort(edge.begin(), edge.end());
        for(int i = 0; i < edge.size(); ++i){
            //printf("%d %d %lld\n", edge[i].a, edge[i].b, edge[i].len);
        }
        for(int i = edge.size() - 1; i >= 0; --i){
            A = find(edge[i].a); B = find(edge[i].b);
            if(A == B) continue; tot++;
            fa[A] = B; ret += edge[i].len; if(tot == n - 1) return ret;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &Q);
    for(int i = 1; i <= n; ++i) MST::fa[i] = i;
    for(int a, b, c, i = 1; i <= Q; ++i){
        scanf("%d%d%d", &a, &b, &c); a++, b++;
        edge.push_back((lpl){a, b, c});
        q.push((lpl){a, nxt(a), c + 1});
        q.push((lpl){b, nxt(b), c + 2});
    }
    lpl now; int tot = 0;
    while(tot != n){
        now = q.top(); q.pop();
        if(!f[now.a]){
            tot++; f[now.a] = 1; edge.push_back((now));
            //printf("now!!!! %d %d %lld\n", now.a, now.b, now.len);
            q.push((lpl){now.b, nxt(now.b), now.len + 2});
        }
    }
    cout << MST::kruscal();
    return 0;
}