#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
#ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
const int maxn = 100005;
int p[maxn], s[maxn];
set<pair<int, pair<int, int>>> edges;
int n, m;
inline int find(int a)
{
return p[a] == a ? a : p[a] = find(p[a]);
}
inline bool unite(int a, int b)
{
a = find(a);
b = find(b);
if (a == b) return false;
if (s[a] < s[b]) swap(a, b);
p[b] = a;
if (s[a] == s[b]) s[a]++;
return true;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edges.insert({c, {a, b}});
edges.insert({c + 1, {a + 1, b}});
}
for (int i = 0; i < n; i++) p[i] = i, s[i] = 0;
ll answer = 0;
while (!edges.empty())
{
int cura = edges.begin()->se.fi % n;
int curb = edges.begin()->se.se % n;
int curc = edges.begin()->fi;
edges.erase(edges.begin());
if (unite(cura, curb))
{
edges.insert({curc + 2, {cura + 1, curb + 1}});
answer += curc;
}
}
cout << answer << endl;
return 0;
}