// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;

const int Maxn = 1e6 + 5;

int N, Q, M, Cnt;

int A, B, C;

ll Ans;

struct Node

{

    int A, B, C;

    bool operator < (const Node &Temp) const

    {

        return C < Temp.C;

    }

}Edge[Maxn];

int H[Maxn], F[Maxn];



int Find(int X)

{

    if (X == F[X]) return X;

    return F[X] = Find(F[X]);

}



int main()

{

    memset (H, 127, sizeof H);

    scanf ("%d %d", &N, &Q);

    for (int i = 1; i < N; ++i) F[i] = i;

    for (int i = 0; i < Q; ++i)

    {

        scanf ("%d %d %d", &A, &B, &C);

        Edge[++Cnt] = Node{A, B, C};

        H[A + 1] = min(H[A + 1], C + 1);

        H[B + 1] = min(H[B + 1], C + 2);

    }

    for (int i = 1; i < (N << 1); ++i) H[i] = min(H[i], H[i - 1] + 2);

    for (int i = 1; i < (N << 1); ++i)

    {

        A = i % N, B = (i - 1) % N;

        Edge[++Cnt] = Node{A, B, H[i]};

    }

    sort (Edge + 1, Edge + Cnt + 1);

    for (int i = 1; i <= Cnt; ++i)

    {

        A = Edge[i].A, B = Edge[i].B, C = Edge[i].C;

        int FA = Find(A), FB = Find(B);

        if (FA != FB) Ans += C, F[FA] = FB;

    }

    printf ("%lld\n", Ans);

}

// Faster C++ solution for the same problem (measured speedup: 1.9301621242288598x):
// #define FNAME "template"



#include <bits/stdc++.h>

using namespace std;



typedef long long inte;

const int maxn = 200005;



#ifndef NDEBUG

#    define dprint(x) (cerr << (#x) << " = "<< (x) << endl)

#else

#    define dprint(x) (NULL)

#endif



template<typename T>

inline void readFig(T& x)

{

#   ifdef FTREAD

        static int c = 0;

        int op = 1;

        x = 0;

        while (!isdigit(c)) {

            if (c == '-')

                op = -1;

            c = getchar();

        }

        while (isdigit(c)) {

            x *= 10;

            x += c - '0';

            c = getchar();

        }

        x *= op;

#   else

        cin >> x;

#   endif

}



struct Edge {

    int u, v;

    inte w;

} edges[maxn * 2];



bool operator <(const Edge& a, const Edge& b)

{

    return a.w < b.w;

}



inte tra[maxn];



int par[maxn];

int getPar(int x)

{

    if (par[x] == x)

        return x;

    else 

        return par[x] = getPar(par[x]);

}



inline void solve()

{

    memset(tra, 0x3f, sizeof(tra));

    int N, Q;

    readFig(N); readFig(Q);

    for (int i = 1; i <= N; ++i)

        par[i] = i;

    for (int i = 1; i <= Q; ++i) {

        inte A, B, C;

        readFig(A); readFig(B); readFig(C);

        edges[i].u = A;

        edges[i].v = B;

        edges[i].w = C;

        tra[A] = min(tra[A], C + 1);

        tra[B] = min(tra[B], C + 2);

    }

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

        tra[(i + 1) % N] = min(tra[(i + 1) % N], tra[i % N] + 2);

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

        const int p = i + Q + 1;

        edges[p].u = i;

        edges[p].v = (i + 1) % N;

        edges[p].w = tra[i];

    }

    const int tot = N + Q;

    sort(edges + 1, edges + tot + 1);

    inte ans = 0;

    int cnt = 0;

    for (int i = 1; i <= tot; ++i) {

        if (getPar(edges[i].u) != getPar(edges[i].v)) {

            par[getPar(edges[i].u)] = getPar(edges[i].v);

            ans += edges[i].w;

            ++cnt;

        }

    }

    assert(cnt == N - 1);

    cout << ans << endl;

}



signed main()

{

#   ifdef FNAME

        freopen(FNAME".in", "r", stdin);

        freopen(FNAME".out", "w", stdout);

#   endif

#   ifndef FTREAD

    	ios::sync_with_stdio(false);

    	cin.tie(0);

#   endif



#   ifdef MULTEST

        int T;

        readFig(T);

        while (T--)

            solve();

#   else

        solve();

#   endif



#   ifdef FNAME

        fclose(stdin);

        fclose(stdout);

#   endif

    	return 0;

}