stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 200010;

struct edge{

	int u,v,w;

}E[maxn*2];

int eid = 0;

int n,m;

namespace ufs{

	int fa[maxn],size[maxn];

	inline void init(){

		for(register int i=0;i<=n;++i) fa[i] = i,size[i] = 1;

	}

	inline int get(int x){

		if(fa[x] == x) return x;

		return fa[x] = get(fa[x]);

	}

	inline void merge(int x,int y){

		int fx = get(x),fy = get(y);

		if(fx == fy) return;

		fa[fy] = fx;

	}

}

ll dis[maxn];

inline bool cmp(const edge &a,const edge &b){

	return a.w < b.w;

}

int main(){

	scanf("%d%d",&n,&m);

	ufs::init();

	memset(dis,0x3f,sizeof dis);

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

		int a,b,c;

		scanf("%d%d%d",&a,&b,&c);

		E[++eid].u = a;

		E[eid].v = b;

		E[eid].w = c;

		dis[a] = min(dis[a],c+1ll);

		dis[b] = min(dis[b],c+2ll);

	}

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

		dis[i] = min(dis[i],dis[(i-1+n)%n]+2);

	}

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

		dis[i] = min(dis[i],dis[(i-1+n)%n]+2);

		E[++eid].u = i;

		E[eid].v = (i + 1) % n;

		E[eid].w = dis[i]; 

	}

	sort(E+1,E+eid+1,cmp);

	int tcnt = 0;

	ll ans = 0;

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

		if(tcnt == n-1) break;

		if(ufs::get(E[i].u) != ufs::get(E[i].v)){

			ans += E[i].w;

			ufs::merge(E[i].u,E[i].v);

			tcnt++;

		}

	}

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4539056443211325x):
#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#define RG register

#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define clear(x, y) memset(x, y, sizeof(x))

#define int long long



inline int read()

{

    int data = 0, w = 1; char ch = getchar();

    while(ch != '-' && (!isdigit(ch))) ch = getchar();

    if(ch == '-') w = -1, ch = getchar();

    while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();

    return data * w;

}



const int maxn(2e5 + 10);

struct edge { int x, y, w; } e[maxn << 2];

inline int cmp(const edge &lhs, const edge &rhs) { return lhs.w < rhs.w; }

int dis[maxn], n, Q, e_num, fa[maxn], ans;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

template<typename T> inline void chkmin(T &x, const T &y) { if(y < x) x = y; }

inline void add_edge(int x, int y, int w) { e[++e_num] = (edge) {x, y, w}; }



signed main()

{

    n = read(), Q = read(); memset(dis, 0x3f, sizeof dis);

    for(RG int i = 1, a, b, c; i <= Q; i++)

        a = read(), b = read(), c = read(),

        add_edge(a, b, c), chkmin(dis[a], c + 1), chkmin(dis[b], c + 2);

    for(RG int i = 0; i < n; i++) chkmin(dis[i], dis[(i - 1 + n) % n] + 2);

    for(RG int i = 0; i < n; i++) chkmin(dis[i], dis[(i - 1 + n) % n] + 2);

    for(RG int i = 0; i < n; i++) add_edge(i, (i + 1) % n, dis[i]), fa[i] = i;

    std::sort(e + 1, e + e_num + 1, cmp);

    for(RG int i = 1; i <= e_num; i++)

    {

        if(find(e[i].x) == find(e[i].y)) continue;

        fa[find(e[i].x)] = find(e[i].y); ans += e[i].w;

    }

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

    return 0;

}
// 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: 5.14794612371425x):
#include<bits/stdc++.h>

#define maxn 800010

#define inf 2000000000

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,q,tot,cnt;

ll ans;

int fa[maxn],val[maxn];

struct edge

{

    int x,y;

    ll v;

}e[maxn];

bool cmp(const edge &a,const edge &b)

{

    return a.v<b.v;

}

int find(int x)

{

    return fa[x]==x?x:fa[x]=find(fa[x]);

}

int main()

{

    read(n),read(q),cnt=n-1;

    for(int i=0;i<n;++i) fa[i]=i,val[i]=inf;

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

    {

        int x,y,v;

        read(x),read(y),read(v);

        e[++tot]={x,y,v},val[x]=min(val[x],v+1),val[y]=min(val[y],v+2);

    }

    for(int i=0;i<=2*n;++i) val[i%n]=min(val[i%n],val[(i-1+n)%n]+2);

    for(int i=0;i<n;++i) e[++tot]={i,(i+1)%n,val[i]};

    sort(e+1,e+tot+1,cmp);

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

    {

        int x=find(e[i].x),y=find(e[i].y);

        if(x==y) continue;

        fa[x]=y,ans+=e[i].v;

        if(++cnt==n-1) break;

    }

    printf("%lld",ans);

    return 0;

}
// 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: 5.148033115708408x):
#include<bits/stdc++.h>

#define maxn 800010

#define inf 2000000000

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,q,tot,cnt;

ll ans;

int fa[maxn],t[maxn];

struct edge

{

    int x,y;

    ll v;

}e[maxn];

bool cmp(const edge &a,const edge &b)

{

    return a.v<b.v;

}

int find(int x)

{

    return fa[x]==x?x:fa[x]=find(fa[x]);

}

int main()

{

    read(n),read(q),cnt=n-1;

    for(int i=0;i<n;++i) fa[i]=i,t[i]=inf;

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

    {

        int x,y,v;

        read(x),read(y),read(v);

        e[++tot]={x,y,v},t[x]=min(t[x],v+1),t[y]=min(t[y],v+2);

    }

    for(int i=0;i<=2*n;++i) t[i%n]=min(t[i%n],t[(i-1+n)%n]+2);

    for(int i=0;i<n;++i) e[++tot]={i,(i+1)%n,t[i]};

    sort(e+1,e+tot+1,cmp);

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

    {

        int x=find(e[i].x),y=find(e[i].y);

        if(x==y) continue;

        fa[x]=y,ans+=e[i].v;

        if(++cnt==n-1) break;

    }

    printf("%lld",ans);

    return 0;

}
// Slower C++ solution:
#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());

}

// Faster C++ solution for the same problem (measured speedup: 13.710398877250277x):
#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<stack>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define qmax(x,y) (x=max(x,y))

#define qmin(x,y) (x=min(x,y))

#define mp(x,y) make_pair(x,y)

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

inline int read(){

	int ans=0,fh=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-') fh=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9')

		ans=ans*10+ch-'0',ch=getchar();

	return ans*fh;

}

const int maxn=2e5+100,inf=2e9;

struct node{

	int x,y,z;

}e[maxn<<1];

int n,a[maxn],m,q,fa[maxn];

ll Ans;

bool cmp(node x,node y){return x.z<y.z;}

int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}

int main(){

//	freopen("nh.in","r",stdin);

//	freopen("zhy.out","w",stdout);

	n=read(),q=read();

	for(int i=0;i<n;i++) a[i]=inf;

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

		int x=read(),y=read(),z=read();

		e[++m]=(node){x,y,z};

		qmin(a[x],z+1),qmin(a[y],z+2);

	}

	for(int i=0;i<n;i++) qmin(a[i],a[(i-1+n)%n]+2);

	for(int i=0;i<n;i++) qmin(a[i],a[(i-1+n)%n]+2);

	for(int i=0;i<n;i++) e[++m]=(node){i,(i+1)%n,a[i]};

	for(int i=0;i<n;i++) fa[i]=i;

	sort(e+1,e+m+1,cmp);

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

		int x=getfa(e[i].x),y=getfa(e[i].y);

		if(x==y) continue;

		fa[x]=y,Ans+=e[i].z;

	}

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

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=4e5+10;

struct Ed{int fr,to,w;}E[N];

int f[N],n,Q,fa[N],cc;

long long Ans;

int cmp(const Ed&A,const Ed&B) {return A.w<B.w;}

int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}

void Work()

{

	for(int i=0;i<=n-2;i++)

		f[i+1]=min(f[i+1],f[i]+2);

	f[0]=min(f[0],f[n-1]+2);

}

int main()

{

	cin>>n>>Q;

	memset(f,63,sizeof(f));

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

	{

		int x,y,w;scanf("%d%d%d",&x,&y,&w);

		E[i]=(Ed){x,y,w};

		f[x]=min(f[x],w+1);

		f[y]=min(f[y],w+2);

	}

	cc=Q;Work();Work();

	for(int i=0;i<=n-2;i++)

		E[++cc]=(Ed){i,i+1,f[i]};

	E[++cc]=(Ed){n-1,0,f[n-1]};

	sort(E+1,E+cc+1,cmp);

	for(int i=1;i<=n;i++) fa[i]=i;

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

	{

		int fx=find(E[i].fr),fy=find(E[i].to);

		if(fx!=fy) Ans+=E[i].w,fa[fx]=fy;

	}

	cout<<Ans<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 13.776485026338218x):
#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<stack>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define qmax(x,y) (x=max(x,y))

#define qmin(x,y) (x=min(x,y))

#define mp(x,y) make_pair(x,y)

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

inline int read(){

	int ans=0,fh=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-') fh=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9')

		ans=ans*10+ch-'0',ch=getchar();

	return ans*fh;

}

const int maxn=2e5+100,inf=2e9;

struct node{

	int x,y,z;

}e[maxn<<1];

int n,a[maxn],m,q,fa[maxn];

ll Ans;

bool cmp(node x,node y){return x.z<y.z;}

int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}

int main(){

//	freopen("nh.in","r",stdin);

//	freopen("zhy.out","w",stdout);

	n=read(),q=read();

	for(int i=0;i<n;i++) a[i]=inf;

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

		int x=read(),y=read(),z=read();

		e[++m]=(node){x,y,z};

		qmin(a[x],z+1),qmin(a[y],z+2);

	}

	for(int i=0;i<n;i++) qmin(a[i],a[(i-1+n)%n]+2);

	for(int i=0;i<n;i++) qmin(a[i],a[(i-1+n)%n]+2);

	for(int i=0;i<n;i++) e[++m]=(node){i,(i+1)%n,a[i]};

	for(int i=0;i<n;i++) fa[i]=i;

	sort(e+1,e+m+1,cmp);

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

		int x=getfa(e[i].x),y=getfa(e[i].y);

		if(x==y) continue;

		fa[x]=y,Ans+=e[i].z;

	}

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

	return 0;

}
// Slower C++ solution:
// luogu-judger-enable-o2

#include<bits/stdc++.h>

using namespace std;

#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )

#define re register

#define int long long

int read() {

	char cc = getchar(); int cn = 0, flus = 1;

	while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }

	while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();

	return cn * flus;

}

const int N = 2e5 + 5 ; 

int n, q, cnt, A[N], B[N], C[N], fa[N], b[N * 2] ; 

struct E {

	int x, y, z ; 

} e[N * 2];

bool cmp( E x, E y ) {

	return x.z < y.z ; 

} 

int fd( int x ) {

	return ( fa[x] == x ) ? x : fa[x] = fd(fa[x]) ;

}

signed main()

{

	n = read(), q = read() ; memset( b, 63, sizeof(b) ) ;

	rep( i, 1, q ) {

		A[i] = read() + 1, B[i] = read() + 1, C[i] = read() ; 

		e[++ cnt].x = A[i], e[cnt].y = B[i], e[cnt].z = C[i] ; 

		b[A[i]] = min( b[A[i]], C[i] + 1 ), b[A[i] + n] = min( C[i] + 1, b[A[i] + n] ),

		b[B[i]] = min( b[B[i]], C[i] + 2 ), b[B[i] + n] = min( C[i] + 2, b[B[i] + n] );

	}

	for( re int i = 2; i <= 2 * n; ++ i )

		b[i] = min( b[i - 1] + 2, b[i] ) ;

	for( re int i = 1; i <= n; ++ i )

		e[++ cnt].x = i, e[cnt].y = ( i == n ) ? 1 : i + 1 , 

		e[cnt].z = min( b[i], b[i + n] ), fa[i] = i;

	sort( e + 1, e + cnt + 1, cmp ) ; int Ans = 0 ;

	rep( i, 1, cnt ) {

		int u = e[i].x, v = e[i].y ;

		u = fd(u), v = fd(v) ;

		if( u == v ) continue ; 

		Ans += e[i].z, fa[u] = v ;

	}

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

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.3361268715875725x):
#include <bits/stdc++.h>



using namespace std;



#define ll long long

#define re register

#define gc getchar()

int read()

{

	re int x(0),f(1);re char ch(gc);

	while(ch>'9'||ch<'0') {if(ch=='-')f=-1;ch=gc;}

	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc;

	return x*f;

}



const int N=2e5+10;



int n,q,m;



struct line {int u,v,w;}e[N<<1];

bool operator < (line a,line b){return a.w<b.w;}

int f[N],v[N];

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

ll ans;



int main()

{

    n=read(),q=read();

    memset(v,127,sizeof(v));

    while(q--)

    {

        int a=read()+1,b=read()+1,c=read();

        e[++m]=(line){a,b,c};

        v[a%n+1]=min(v[a%n+1],c+1);

        v[b%n+1]=min(v[b%n+1],c+2);

    }

    int pos(1);

    for(int i=2;i<=n;++i)

        if(v[i]<v[pos])

            pos=i;

    for(int i=pos%n+1,j=pos;i!=pos;j=i,i=i%n+1)

        v[i]=min(v[i],v[j]+2);

    for(int i=2;i<=n;++i)

        e[++m]=(line){i-1,i,v[i]};

    e[++m]=(line){1,n,v[1]};

    sort(e+1,e+1+m);

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

        f[i]=i;

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

    {

        int u=find(e[i].u),v=find(e[i].v);

        if(u==v) continue;

        ans+=e[i].w;f[u]=v;

    }

    cout<<ans<<'\n';

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <cctype>

#include <cstring>

#include <cstdio>



using namespace std;



#define M 800005

#define ll long long



int n, q, tot;

int fa[M];

ll ans, d[M];



struct Edge

{ int u, v; ll w; } e[M];



inline int read()

{

	int x = 0, f = 1; char ch = getchar();

	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }

	while (isdigit(ch)) { (x *= 10) += ch - '0'; ch = getchar(); }

	return x * f;

}



inline int findf(int x)

{ return fa[x] == x ? x : fa[x] = findf(fa[x]); }



inline bool cmp1(Edge a, Edge b)

{ return a.w < b.w; }



inline void kruscal()

{

	sort(e + 1, e + 1 + tot, cmp1);

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

	{

		int uf = findf(e[i].u), vf = findf(e[i].v);

		if (uf == vf) continue;

		fa[uf] = vf; ans += e[i].w;

	}

}



int main()

{

	n = read(), q = read(); tot = q;

	for (int i = 0; i < n; i++) fa[i] = i;

	memset(d, 0x3f3f3f3f, sizeof(d));

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

	{

		e[i].u = read(), e[i].v = read(); e[i].w = read();

		d[e[i].u] = min(d[e[i].u], e[i].w + 1);

		d[e[i].v] = min(d[e[i].v], e[i].w + 2);

	}



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

		d[i] = min(d[i], d[(i-1+n)%n] + 2);

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

		d[i] = min(d[i], d[(i-1+n)%n] + 2);



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

		e[++tot].u = i, e[tot].v = (i+1)%n, e[tot].w = d[i];



	kruscal();



	cout << ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.9575839983537344x):
#include <bits/stdc++.h>

using namespace std;



inline int read()

{

	int x=0,f=1,c=getchar();

	while(c<48) c=='-'&&(f=-1),c=getchar();

	while(c>47) x=x*10+c-'0',c=getchar();

	return x*f;

}



const int MAXN = 400005;

struct Edge {int u,v,w;} e[MAXN];

int fa[MAXN],f[MAXN];

int n,m,q;



inline int find(int x)

{return x^fa[x]?fa[x]=find(fa[x]):x;}



inline void merge(int x,int y)

{((x=find(x))^(y=find(y)))&&(fa[x]=y);}



int main(int argc,char const *argv[])

{

	n=read(); q=read();

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

	for(int i=1,a,b,c; i<=q; ++i)

	{

		a=read()+1,b=read()+1,c=read();

		f[a%n+1]=min(f[a%n+1],c+1);

		f[b%n+1]=min(f[b%n+1],c+2);

		e[++m]=Edge{a,b,c};

	}

	int pos=1;

	for(int i=2; i<=n; ++i) if(f[i]<f[pos]) pos=i;

	for(int i=pos%n+1,j=pos; i!=pos; j=i,i=i%n+1)

		f[i]=min(f[i],f[j]+2);

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

		e[++m]=Edge{i,i+1,f[i+1]};

	e[++m]=Edge{n,1,f[1]};

	sort(e+1,e+m+1,[](Edge a,Edge b) {return a.w<b.w;});

	for(int i=1; i<=n; ++i) fa[i]=i;

	long long tot=0,ans=0;

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

	{

		int u=e[i].u,v=e[i].v,w=e[i].w;

		if(find(u)==find(v)) continue;

		++tot,ans+=w,merge(u,v);

		if(tot==n-1) break;

	}

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

	return 0;

}
// Slower C++ solution:
#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <vector>

#define itn int

#define reaD read

#define N 200001

using namespace std;



int n, Q, f[N], cnt, fa[N]; 

struct edge { int from, to, cost; bool operator < (const edge &p) const { return cost < p.cost; } } e[N << 2]; 



inline int read()

{

	int x = 0, w = 1; char c = getchar();

	while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }

	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }

	return x * w;

}



inline void adde(int u, int v, int w) { e[++cnt] = (edge) { u, v, w }; }



int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }



long long Kruscal()

{

	sort(e + 1, e + cnt + 1); 

	long long ans = 0; 

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

	{

		int u = find(e[i].from), v = find(e[i].to), w = e[i].cost; 

		if(u == v) continue; 

		fa[u] = v; ans += w; 

	}

	return ans; 

}



int main()

{

	n = read(); Q = read();

	for(int i = 1; i <= n; i++) fa[i] = i; 

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

	while(Q--)

	{

		int u = read() + 1, v = read() + 1, w = reaD();

		adde(u, v, w); 

		f[u] = min(f[u], w + 1); f[v] = min(f[v], w + 2); 

	}

	int pos = 1; 

	for(int i = 2; i <= n; i++) if(f[i] < f[pos]) pos = i; 

	for(int i = pos; i <= pos + n - 1; i++) f[i % n + 1] = min(f[i % n + 1], f[(i - 1) % n + 1] + 2); 

	for(int i = 1; i <= n; i++) adde(i, i % n + 1, f[i]);

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8060999506446742x):
#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define maxn 600000

#define inf 2e18

#define int long long

using namespace  std;

int newp=0,first[maxn+4]={0},st[maxn+4]={0},fa[maxn+4]={0}; 

struct edge{

	int l,r,w;

}e[maxn+4];

bool cmp(edge x,edge y){

	return x.w<y.w;

}

void add(int x,int y,int z){

	e[++newp]=(edge){y,first[x],z};

	first[x]=newp;

}

int find(int x){

	return x==fa[x]?x:fa[x]=find(fa[x]);

}

signed main(){

	int n,q;

	scanf("%lld%lld",&n,&q);

	int u,v,w;

	for(int i=0;i<n;i++)st[i]=inf;

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

		scanf("%lld%lld%lld",&u,&v,&w);

		e[++newp]=(edge){u,v,w};

		if(u==v)st[u]=min(st[u],w+1);

		st[u]=min(st[u],w+1);

		st[v]=min(st[v],w+2);

	}

	int ans=inf,re;

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

		st[i]=min(st[i],st[(i-1+n)%n]+2);

	}

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

		st[i]=min(st[i],st[(i-1+n)%n]+2);

	}

/*	for(int i=0;i<=n-1;i++)

		if(st[i]<ans){

			ans=st[i];

			re=i;

		}

	/*for(int i=0;i<=(n-1);i++){

		int j=(re+i)%n;

		st[j]=min(st[j],ans);

		ans=min(st[j],ans);

		ans+=2;

	}*/

	for(int i=0;i<=(n-1);i++)

		e[++newp]=(edge){i,(i+1)%n,st[i]};

	sort(e+1,e+newp+1,cmp);

	int cnt=0,ret=0;

	for(int i=0;i<n;i++)fa[i]=i;

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

		int u=e[i].l,v=e[i].r;

		if(find(u)!=find(v)){

			fa[find(u)]=find(v);

			cnt++;

			ret+=e[i].w;

			if(cnt==n-1)break;

		}

	}

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

	return 0;

 }
// Slower C++ solution:
# include <iostream>

# include <deque>

using namespace std;



string S;

int K;

deque<int> d;

int counter=0;

long long ans=0;

bool allsame=true;



int main()

{

    cin>>S;

    cin>>K;



    char current=S[0];



    for (int i=0; i<S.size(); i++)

    {

        if (S[i]==current)

        {

            counter++;

        }



        else

        {

            d.push_back(counter);

            counter=1;

            current=S[i];

        }

    }



    d.push_back(counter);



    for (int i=0; i<d.size(); i++)

    {

        if (d[i]>1)

        {

            ans=ans+(d[i]/2);

        }

    }



    for (int i=0; i<S.size(); i++)

    {

        current=S[0];

        if (S[i]!=current)

        {

            allsame=false;

            break;

        }

    }



    if (allsame)

    {

        ans=1ll*K*S.size()/2;



    }



    else if (d.front()%2==1 && d.back()%2==1 && S[0]==S[S.size()-1])

    {

        ans=ans*K;

        ans=ans+K-1;

    }



    else

    {

        ans=ans*K;

    }



    cout<<ans<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.265079798481669x):
#include<cstdio>

#include<cstring>

using namespace std;



char s[102];

int a[101];

int main(){

	scanf("%s",s+1);

	int n=strlen(s+1),k;

	scanf("%d",&k);

	for(int i=1,o=1;i<=n;i++){

		if(s[i]!=s[i+1]){

			a[++a[0]]=i-o+1;

			o=i+1;

		}

	}

	long long ans=0;

	if(s[1]==s[n]){

		if(a[0]==1)ans=1ll*n*k/2;

		else{

			for(int i=2;i<a[0];i++)

				ans+=1ll*a[i]/2*k;

			ans+=a[1]/2+a[a[0]]/2;

			ans+=1ll*(a[1]+a[a[0]])/2*(k-1);

		}

	}

	else for(int i=1;i<=a[0];i++)

		ans+=1ll*a[i]/2*k;

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

}