#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using U = unsigned int;
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using std::cin; using std::cout;
using std::endl; using std::cerr;
using std::bitset; using std::map;
using std::queue; using std::priority_queue;
using std::set; using std::string;
using std::vector;
using std::pair; using std::make_pair;
using pii = std::pair<int, int>;
using pll = std::pair<LL, LL>;
#ifdef LOCAL
#include <ctime>
void displayTime() { cout << "Current time = " << clock() * 1e3 / CLOCKS_PER_SEC << "ms" << endl; }
#else
void displayTime() {}
#endif
#ifdef DEBUG
#define pass cerr << "[" << __FUNCTION__ << "] : line = " << __LINE__ << endl;
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n) { cerr << #a << " = {"; \
      for(int qwq = (st); qwq <= (n); ++qwq) cerr << a[i] << (qwq == n ? ' ' : '\n'); }
#else
#define pass ;
#define display(x) ;
#define displaya(a, st, n) {}
#endif

template<typename T1, typename T2>
inline bool chmin(T1 &a, const T2 &b) { return a > b ? a = b, true : false; }
template<typename T1, typename T2>
inline bool chmax(T1 &a, const T2 &b) { return a < b ? a = b, true : false; }
#ifdef QUICK_READ
char pool[1<<15|1],*it=pool+32768;
#define getchar() (it>=pool+32768?(pool[fread(pool,sizeof(char),1<<15,stdin)]=EOF,*((it=pool)++)):*(it++))
#endif
inline int readint() {
  int a = 0; char c = getchar(), p = 0;
  while(isspace(c)) c = getchar();
  if(c == '-') p = 1, c = getchar();
  while(isdigit(c)) a = a*10 + c - '0', c = getchar();
  return p ? -a : a;
}
inline LL readLL() {
  LL a = 0; char c = getchar(), p = 0;
  while(isspace(c)) c = getchar();
  if(c == '-') p = 1, c = getchar();
  while(isdigit(c)) a = a*10 + c - '0', c = getchar();
  return p ? -a : a;
}

const int maxN = 200000 + 5;
const int maxQ = 200000 + 5;
const int INF = 0x3f3f3f3f;
int n, q;
int mn[maxN];
struct Edge {
  int from, to, dist;
  Edge() {}
  Edge(int f, int t, int d) : from(f), to(t), dist(d) {}
  friend bool operator < (const Edge &A, const Edge &B) {
    return A.dist < B.dist;
  }
}edges[maxN + maxQ];
int pa[maxN];
int findpa(int x) {
  return pa[x] == x ? x : pa[x] = findpa(pa[x]);
}
int m = 0;
void addedge(int x, int y, int z) {
  edges[m++] = Edge(x, y, z);
}

int main() {
  n = readint(); q = readint();
  memset(mn, INF, sizeof(mn));
  for(int i = 1; i <= q; ++i) {
    int x = readint(), y = readint(), z = readint();
    addedge(x, y, z);
    chmin(mn[x], z + 1);
    chmin(mn[y], z + 2);
  }
  for(int i = 1; i < n; ++i) chmin(mn[i], mn[i - 1] + 2);
  chmin(mn[0], mn[n - 1] + 2);
  for(int i = 1; i < n; ++i) chmin(mn[i], mn[i - 1] + 2);
  for(int i = 0; i < n; ++i) addedge(i, i + 1 < n ? i + 1 : 0, mn[i]);
  std::sort(edges, edges + m);
  for(int i = 0; i < n; ++i) pa[i] = i;
  LL ans = 0;
  for(int i = 0; i < m; ++i) {
    int x = edges[i].from, y = edges[i].to, z = edges[i].dist;
    int fx = findpa(x), fy = findpa(y);
    if(fx == fy) continue;
    pa[fx] = fy; ans += z;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 9600