#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define setNil(x) memset((x),0,sizeof(x))
#define setINF(x) memset((x),63,sizeof(x))
#define setNegINF(x) memset((x),192,sizeof(x)) //NegINF=-INF-1
#define setNeg1(x) memset((x),255,sizeof(x))
#define MP make_pair
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,q,f[200005],cnt;
ll res;
priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > > pq;
inline int fnd(int x){
	return f[x]==x?x:f[x]=fnd(f[x]);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q;
	for(int i=0;i<n;i++)f[i]=i;
	while(q--){
		int a,b,c;
		cin>>a>>b>>c;
		pq.push(MP(c,MP(a,b)));
		pq.push(MP(c+1,MP((a+1)%n,b)));
	}
	while(!pq.empty()){
		int u=pq.top().Y.X,v=pq.top().Y.Y,c=pq.top().X;
		pq.pop();
		if(fnd(u)==fnd(v))continue;	
		f[fnd(u)]=fnd(v);
		res+=c;
		if((++cnt)==n-1)break;
		pq.push(MP(c+2,MP((u+1)%n,(v+1)%n)));
	}
	cout<<res<<endl;
	return 0;
}