#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <ctime>
#include <deque>
using namespace std;

int n, q, a[210000], b[210000], c[210000], fa[210000], d[210000];
long long ans;
vector <int> now, now1;
int co;
int tx[210000];
set <pair<int, int> > used;

bool cmp(int x, int y) {
	return c[x] < c[y];
}

int gf(int x) {
	if (fa[x] != x)
		fa[x] = gf(fa[x]);
	return fa[x];
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= q; i++) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
	}
	for (int i = 1; i <= q; i++)
		tx[i] = i;
	sort(tx + 1, tx + q + 1, cmp);
	for  (int i = 1; i <= n; i++)
		fa[i] = i;
	co = n;
	c[tx[q + 1] = q + 1] = 2000000000;
	int h;
	for (int i = 1; i <= q; i = h + 1) {
		h = i;
		while (h < q && c[tx[h + 1]] == c[tx[i]])
			h ++;
		for (int j = i; j <= h; j++)
			now.push_back(tx[j]);
		while (now.size() > 0 && c[now[0]] < c[tx[h + 1]] && co > 1) {
			now1.clear();
			for (int j = 0; j < (int) now.size(); j++) {
				if (gf(a[now[j]]) != gf(b[now[j]])) {
					fa[gf(a[now[j]])] = gf(b[now[j]]);
					co -= 1;
					ans += c[now[j]];
				}else {
					d[now[j]] |= (1 << (c[now[j]] % 2));
				}
			}
			for (int j = 0; j < (int) now.size(); j++)
				if (d[now[j]] != 3)
					now1.push_back(now[j]);
			now.clear();
			for (int j = 0; j < (int) now1.size(); j++)
				now.push_back(now1[j]);
			for (int j = 0; j < (int) now.size(); j++) {
				swap(a[now[j]], b[now[j]]);
				b[now[j]] = (b[now[j]] + 1) % n;
				c[now[j]] += 1;
			}
		}
	}
	cout << ans << endl;
}