#include <bits/stdc++.h>
using namespace std;

struct edge
{
  long long d;
  int a,b;
};

bool operator<(edge e1,edge e2)
{
  return e1.d>e2.d;
}

int rt(int *uf,int i)
{
  return uf[i]<0?i:uf[i]=rt(uf,uf[i]);
}

void con(int *uf,int a,int b)
{
  a=rt(uf,a);
  b=rt(uf,b);
  if(a!=b){
    if(-uf[a]<-uf[b]){
      uf[a]=b;
    }
    else if(-uf[a]>-uf[b]){
      uf[b]=a;
    }
    else{
      uf[a]=b;
      uf[b]--;
    }
  }
}


int main()
{
  int n,q;
  scanf("%d%d",&n,&q);
  priority_queue<edge> Q;
  for(int i=0;i<q;i++){
    int a,b;
    long long c;
    scanf("%d%d%lld",&a,&b,&c);
    edge e;
    e.a=a,e.b=b,e.d=c;
    Q.push(e);
    edge e2;
    e2.a=(a+1)%n,e2.b=b,e2.d=c+1;
    Q.push(e2);
  }
  long long A=0;
  static int uf[200000];
  for(int i=0;i<n;i++){
    uf[i]=-1;
  }
  int N=n;
  while(N>1){
    edge e=Q.top();
    Q.pop();
    int a=e.a,b=e.b;
    long long c=e.d;
    int r1=rt(uf,a),r2=rt(uf,b);
    //printf("%d %d %lld\n",a,b,c);
    if(r1!=r2){
      A+=c;
      N--;
      con(uf,r1,r2);
      edge ne;
      ne.d=c+2;
      ne.a=(a+1)%n;
      ne.b=(b+1)%n;
      Q.push(ne);
    }
  }
  printf("%lld\n",A);
  return 0;
}

