#include <algorithm>
#include <cstdio>
struct edge
{
int u, v, w;
edge(int _u = 0, int _v = 0, int _w = 0)
{
u = _u;
v = _v;
w = _w;
}
inline bool operator <(const edge &a) const
{
return w < a.w;
}
} arr[400005];
int fa[400005], w[400005];
int getfa(int u)
{
if (u == fa[u])
return u;
return fa[u] = getfa(fa[u]);
}
int main()
{
// freopen("CF16-final-G.in", "r", stdin);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
fa[i] = i;
w[i] = w[i + n] = 2e9;
}
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &arr[i].u, &arr[i].v, &arr[i].w);
w[arr[i].u] = std::min(w[arr[i].u], arr[i].w + 1);
w[arr[i].v] = std::min(w[arr[i].v], arr[i].w + 2);
}
for (int i = 1; i < n << 1; i++)
w[i] = std::min(w[i - 1] + 2, w[i]);
for (int i = 0; i < n; i++)
arr[m++] = edge(i, (i + 1) % n, std::min(w[i], w[i + n]));
std::sort(arr, arr + m);
long long ans = 0;
for (int i = 0; i < m; i++)
{
int u = getfa(arr[i].u), v = getfa(arr[i].v);
if (u != v)
{
fa[u] = v;
ans += arr[i].w;
}
}
printf("%lld\n", ans);
return 0;
}