// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200200;

int u[maxn], to[maxn];

long long best[maxn];

void init(){ 

	for(int i = 0; i < maxn; i++){

		u[i] = i;

		to[i] = -1;

		best[i] = 1ll<<60;

	}

}

int find(int x){

	if(x == u[x]) return x;

	return u[x] = find(u[x]);

}

long long cost[maxn];

vector<pair<int,int> > e[maxn];

int main(){

	int n, q; cin >> n >> q;

	for(int i = 0; i < n; i++) cost[i] = 1ll<<60;

	for(int i = 0; i < q; i++){

		int a, b; long long c; cin >> a >> b >> c;

		cost[a] = min(cost[a], c + 1);

		cost[b] = min(cost[b], c + 2);

		e[a].push_back({b, c});

		e[b].push_back({a, c});

	}

	for(int i = 0; i < 2 * n; i++){

		int now = i % n; 

		int prv = now - 1; if(prv < 0) prv += n;

		cost[now] = min(cost[now], cost[prv] + 2);

	}

	auto dist = [&](int u, int v){

		if(u == v) return 0ll;

		long long ans = 1ll<<60;

		for(int rot = 0; rot < 2; rot++){

			swap(u, v);

			if(u < v){

				ans = min(ans, cost[u] + (v - u - 1) * 2);

				ans = min(ans, cost[v] + (n - v + u - 1) * 2);

			}

		}		

		return ans;

	};

	init();

	set<int> all;

	for(int i = 0; i < n; i++){

		all.insert(i);

	}

	int comps = n;

	long long ans = 0;

	while(comps > 1){

		vector<pair<int,int> > vert;

		for(int i = 0; i < n; i++){

			vert.push_back({find(i), i});

			to[find(i)] = -1;

			best[find(i)] = 1ll<<60;

		}

		sort(vert.begin(), vert.end());

		int j = 0;

		for(int i = 0; i < n; i = j){

			while(j < n && vert[j].first == vert[i].first) j++;

			for(int k = i; k < j; k++) all.erase(vert[k].second);

			int head = vert[i].first;

			for(int k = i; k < j; k++){

				auto it = all.lower_bound(vert[k].second);

				int going;

				if(it == all.end()) going = *all.begin();

				else going = *it;

				long long d = dist(vert[k].second, going);

				int hgo = find(going);

				if(best[head] > d) best[head] = d, to[head] = going;

				if(best[hgo] > d) best[hgo] = d, to[hgo] = head;

			}

			for(int k = i; k < j; k++) all.insert(vert[k].second);

		}

		for(int i = 0; i < n; i++){

			int head = find(i);

			for(auto ed : e[i]){

				if(find(ed.first) != head){

					if(best[head] > ed.second){

						best[head] = ed.second;

						to[head] = ed.first;

					}

					if(best[find(ed.first)] > ed.second){

						best[find(ed.first)] = ed.second;

						to[find(ed.first)] = head;

					}

				}

			}

		}

		vector<pair<long long, int>> heads;

		for(int i = 0; i < n; i++) if(i == find(i)) heads.push_back({best[i], i});

		sort(heads.begin(), heads.end());

		for(auto h : heads){

			int head = h.second;

			if(find(head) != find(to[head])){

				ans += best[head];

				comps--;

				u[find(head)] = find(to[head]);

			}

		}

	}

	cout << ans << endl;

	return 0;

}




// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200200;

int u[maxn];

int find(int x){

	if(x == u[x]) return x;

	return u[x] = find(u[x]);

}

long long cost[maxn];

int main(){

	iota(u, u + maxn, 0);

	int n, q; cin >> n >> q;

	for(int i = 0; i < n; i++) cost[i] = 1ll<<60;

	vector<tuple<int,int,int> > ed;

	for(int i = 0; i < q; i++){

		int a, b; long long c; cin >> a >> b >> c;

		cost[a] = min(cost[a], c + 1);

		cost[b] = min(cost[b], c + 2);

		ed.push_back(make_tuple(c, a, b));

	}

	for(int i = 0; i < 2 * n; i++){

		int now = i % n; 

		int prv = now - 1; if(prv < 0) prv += n;

		cost[now] = min(cost[now], cost[prv] + 2);

	}

	for(int i = 0; i < n; i++) ed.push_back(make_tuple(cost[i], i, (i + 1) % n));

	sort(ed.begin(), ed.end());

	long long ans = 0;

	for(auto e : ed){

		int w, x, y; tie(w, x, y) = e;

		if(find(x) != find(y)){

			ans += w;

			u[find(x)] = find(y);

		}

	}

	cout << ans << endl;

	return 0;

}


// Fastest known solution for this problem: