#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
typedef long long i64;
const int N = 200000 + 10;
struct Edge {
int x, y, z;
Edge() {}
Edge(int _x, int _y, int _z): x(_x), y(_y), z(_z) {}
inline bool operator< (const Edge &rhs) const {
return z < rhs.z;
}
};
inline void check(int &lhs, int rhs) { lhs = (lhs < rhs ? lhs : rhs); }
int n, tag[N];
std::vector<Edge> edge;
void init() {
int m;
scanf("%d%d", &n, &m);
memset(tag, 0x3f, sizeof tag);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edge.push_back(Edge(a, b, c));
check(tag[a], c + 1);
check(tag[b], c + 2);
}
for (int i = 0; i < 3 * n; ++i) check(tag[(i + 1) % n], tag[i] + 2);
}
int anc[N];
int find(int x) { return anc[x] == x ? x : (anc[x] = find(anc[x])); }
int main() {
init();
for (int i = 0; i < n; ++i) edge.push_back(Edge(i, (i + 1) % n, tag[i]));
std::sort(edge.begin(), edge.end());
for (int i = 0; i < n; ++i) anc[i] = i;
i64 ans = 0;
for (int i = 0; i < edge.size(); ++i) {
int x = find(edge[i].x), y = find(edge[i].y), z = edge[i].z;
if (x != y) anc[x] = y, ans += z;
}
printf("%lld\n", ans);
return 0;
}