#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge
{
	int u , v;
	ll w;
}E[400010];
int len , head[200010];
void add(int u , int v , ll w)
{
	E[len++] = {u , v , w};
	
}
bool cmp(edge a , edge b)
{
	return a.w < b.w;
}
int n , a , b , q;
int fa[200010];
ll d[200010];
int get(int x)
{
	return (fa[x] == x) ? x : (fa[x] = get(fa[x]));
}
ll kruskal()
{
	ll res = 0;
	int cnt = n;
	sort(E , E + len , cmp);
	for (int i = 0; i < len; i++)
	{
		int u = E[i].u , v = E[i].v;
		ll w = E[i].w;
		//cout << u << " " << v << " " << w << endl;
		u = get(u) , v = get(v);
		if (u != v)
		{
			fa[v] = u;
			res += w;
			cnt--;
		}
		if (cnt == 1)
		{
			return res;
		}
	}
	return res;
}
int main()
{
	memset(d , 0x7f , sizeof(d));
	ll c;
	scanf("%d%d" , &n , &q);
	for (int i = 0; i < n; i++)
	{
		fa[i] = i;
	}
	for (int i = 1; i <= q; i++)
	{
		scanf("%d%d%lld" , &a , &b , &c);
		add(a , b , c);
		d[a] = min(d[a] , c + 1);
		d[b] = min(d[b] , c + 2);
		//cout << a << "  " << b <<" " << d[a] << " " << d[b] << endl;
	}
	for (int i = 0; i < n; i++)
	{
		d[(i + 1) % n] = min(d[(i + 1) % n] , d[i] + 2);
	}
	for (int i = 0; i < n; i++)
	{
		d[(i + 1) % n] = min(d[(i + 1) % n] , d[i] + 2);
	}
	for (int i = 0; i < n; i++)
	{
		add(i , (i + 1) % n , d[i]);
	}
	printf("%lld\n" , kruskal());
}