stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
///AJoy Sarker ,CSE JAHANGIRNAGAR UNIVERSITY 48 Batch

#include<bits/stdc++.h>

using namespace std;

#define SORT(c) sort((c).begin(),(c).end());

#define pb push_back

#define MP make_pair

#define pii pair<int,int>

#define pcc pair<char,char>

#define pic pair<int,char>

#define pci pair<char,int>

#define VS vector<string>

#define VI vector<int>

#define pi 3.141592653589793

#define ll long long

#define ull unsigned long long

#define w(x) int x;cin>>x;while(x--)

#define fast ios_base::sync_with_stdio(0)

#define sz size()

typedef unsigned long long UL;

template<typename T>inline T  S(T a)

{

    return a*a;

}

template<class T>inline string tostring(T a)

{

    ostringstream os("");

    os << a;

    return os.str();

}

template<typename T>inline ll tolong(T a)

{

    ll res;

    istringstream os(a);

    os>>res;

    return res;

}

template<typename T>inline T gcd(T a, T b)

{

    if (b == 0)return a;

    else return gcd(b, a % b);

}

template<typename T>inline T bigmod(T a, T b, T m)

{

    if (b == 0)return 1;

    else if (b % 2 == 0)return S(bigmod(a, b / 2, m)) % m;

    else return (a % m*bigmod(a, b - 1, m)) % m;

}

const int inf = (int)1e9 + 5;

const ll linf = (ll)1e16 + 5;

const ll modd = (ll)1e9 + 7;

const int mod = 10000007;

/*#define N 20000009

bool prime[N];

vector<ll> prm;

void seive ()

{



    memset(prime, true, sizeof(prime));



    for( ll i=2; i*i<=N; i++)

    {

        if (prime[i] == true)

        {

            prm.pb(i);

            for (ll j=i*i; j<=N; j += i)

                prime[j] = false;

        }

    }

}*/

void pr (int f)

{

    if(f==1)

        cout<<"Yes\n";

    else

        cout<<"No\n";

}

map<int,int>mp;

multiset<string> st;

multiset<string> :: iterator it;



deque <char> q ;

int vis [1000];

int main()

{

    fast ;

   char c;

   cin >> c ;

  if(c =='a' || c=='e' || c == 'i' || c =='o' || c=='u')

  cout <<"vowel\n";

else

   cout <<"consonant\n";

}












// Optimized solution to the same problem (faster):
#include <cstdio>



int main() {

	char ch;

	scanf("%c", &ch);

	if (ch == 'a' || ch == 'o' || ch == 'e' || ch == 'i' || ch == 'u')

		puts("vowel");

	else puts("consonant");

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long int

using namespace std;

int main()

{

    ll t,a,b,i,j,k,n,x;

    char c;

    cin>>c;

    if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')

    {

        cout<<"vowel"<<endl;

    }

    else

        cout<<"consonant"<<endl;

     return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



int main() {

	char ch;

	scanf("%c", &ch);

	if (ch == 'a' || ch == 'o' || ch == 'e' || ch == 'i' || ch == 'u')

		puts("vowel");

	else puts("consonant");

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;



int main()

{

string c;

cin>>c;

if(c=="a"|| c=="e"||c=="i"||c=="o"||c=="u")

    cout<<"vowel";

else

    cout<<"consonant";

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



int main() {

	char ch;

	scanf("%c", &ch);

	if (ch == 'a' || ch == 'o' || ch == 'e' || ch == 'i' || ch == 'u')

		puts("vowel");

	else puts("consonant");

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

#include<set>

#include<list>

#include<stack>

#include<vector>

#include<cstdlib>

#include<iterator>

#include<deque>

#include<ctime>

#include<iomanip>

#include<map>

#include<bitset>

#include<utility>

#include<sstream>

using namespace std;

int main()

{

	char c;

	cin>>c;

	if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')printf("vowel");

	 else printf("consonant");

	return 0;

}




// Optimized solution to the same problem (faster):
#include<cstdio>

char n;

int main()

{

	scanf("%s",&n);

	if (n=='a'||n=='e'||n=='i'||n=='o'||n=='u')printf("vowel");

	else printf("consonant");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<iomanip>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<vector>

#include<cctype>

#define I insert

#define SG getchar()

using namespace std;

set<char> uoi;

signed main()

{

	uoi.I('a'),uoi.I('e'),uoi.I('i'),uoi.I('o'),uoi.I('u');

	puts(((uoi.count(SG))?("vowel"):("consonant")));

	return 0;

}

// Optimized solution to the same problem (faster):
#include "stdio.h"

int main()

{

	char c=getchar();

	printf(c!='a'&&c!='e'&&c!='i'&&c!='o'&&c!='u'?"consonant\n":"vowel\n");

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <string>

 

int main()

{

  char c;

  scanf("%c", &c);

  std::string s("aeiou");

  if (s.find(c) != -1)

    printf("vowel\n");

  else

    printf("consonant\n");

  return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

 

int main()

{

  char c;

  scanf("%c", &c);

  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')

    printf("vowel\n");

  else

    printf("consonant\n");

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <cstdlib>





using namespace std;



int main()

{

    string Letter;

    string Vowel[] = {"a","e","i","o","u"};

    cin >> Letter;

    if(Letter == Vowel[0] || Letter == Vowel[1] || Letter == Vowel[2] || Letter == Vowel[3] || Letter == Vowel[4]){

        cout << "vowel" << endl;

    }else{

        cout << "consonant" << endl;

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main(){

	char c;

	c = getchar();

	if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')	

	{

		printf("vowel\n");

		}

		else {printf("consonant\n");}

	return 0;

	}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<algorithm>

#include<cstdio>

#include<cstring>

#define N 500000

#define NN 200005

using namespace std;

struct ahh{

	int u,v,next;

	long long w;

}a[N];

int fa[NN],head[NN],n,m,tot,x,y;

long long sum,best[NN],v;

void add(int u,int v,long long w){

	tot++;

	a[tot].u=u;a[tot].v=v;a[tot].w=w;

}

bool cmp(ahh x,ahh y){return (x.w<y.w);}

int find(int x){

	if (fa[x]!=x)fa[x]=find(fa[x]);

	return fa[x];

}

void Union(int x,int y){

	int x1=find(x);

	int y1=find(y);

	if (x1!=y1)fa[y1]=x1;

}

void kruskal(){

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

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

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

		if (find(a[i].u)!=find(a[i].v))Union(a[i].u,a[i].v),sum+=a[i].w;

}

int main(){

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

	tot=0;

	sum=0;

	memset(best,127,sizeof(best));

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

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

		scanf("%d%d%lld",&x,&y,&v);

		add(x,y,v);

		best[x%n]=min(best[x%n],v+1);

		best[y%n]=min(best[y%n],v+2);

	}

	for (int t=0;t<2;t++)

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

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

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

		add(i,(i+1)%n,best[i]);

	}

	kruskal();

	printf("%lld",sum);

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fin(x) freopen(x,"r",stdin)

#define fout(x) freopen(x,"w",stdout)

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pii;

const ll INF=0x3f3f3f3f3f3f3f3f;

const ll inf=0xc0c0c0c0c0c0c0c0;

const double pi=acos(-1);

const ll MAX=2e5+7;

ll N,Q;

struct node{

	ll A,B,C;

};

bool operator<(node n1,node n2){return n1.C>n2.C;}

ll fa[MAX];

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

priority_queue<node>que;

int main()

{

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

	for(ll i=0;i<N;i++)

		fa[i]=i;

	while(Q--)

	{

		node n;

		scanf("%lld%lld%lld",&n.A,&n.B,&n.C);

		que.push(n);

		n.A=(n.A+1)%N;n.C++;

		que.push(n);

	}

	ll block=N;

	ll res=0;

	while(block!=1)

	{

		node n=que.top();

		que.pop();

		ll a=find(n.A),b=find(n.B);

		if(a!=b)

		{

			res+=n.C;

			fa[a]=b;

			n.A=(n.A+1)%N;

			n.B=(n.B+1)%N;

			n.C+=2;

			block--;

			que.push(n);

		}

		// prllf("%lld\n",block);

	}

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

long long n,m,cnt = 0;

long long dis[200010];

struct edge {

	long long u,v,len;

}e[500010];

long long fa[200010];

bool cmp(edge x,edge y){

	return x.len<y.len;

}

long long get(long long x){

	if (fa[x]==x){

		return x;

	}

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

}

int main () {

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

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

		fa[i] = i;

		dis[i] = 1e18;

	}

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

		long long a,b,c;

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

		e[++cnt].u = a;

		e[cnt].v = b;

		e[cnt].len = c;

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

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

	}

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

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

	}

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

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

	}

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

		e[++cnt].u = i;

		e[cnt].v = (i+1)%n;

		e[cnt].len = dis[i];

	}

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

	long long ans = 0,ccnt = 0;

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

		int fx = get(e[i].u);

		int fy = get(e[i].v);

		//cout << fx << " " << fy << " " << e[i].len << endl;

		if (fx!=fy){

			fa[fx] = fy;

			ans += e[i].len;

			ccnt++;

		}

		if (ccnt==n-1){

			break;

		}

	}

	printf("%lld",ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gt getchar()

#define ll long long

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

typedef std::pair<int,int> P;

#define mk std::make_pair

#define fr first

#define sc second

inline int in()

{

	int k=0;char ch=gt;bool p=1;

	while(ch<'-')ch=gt;if(ch=='-')ch=gt,p=0;

	while(ch>'-')k=k*10+ch-'0',ch=gt;

	return p?k:-k;

}

const int N=2e5+5;

int f[N],fa[N];

struct node{int u,v,w;}E[N<<2];

inline bool operator<(const node &a,const node &b){return a.w<b.w;}

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

int main()

{

	int n=in(),Q=in(),tot=Q;

	memset(f,0x3f,n<<2);

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

	{

		int u=in(),v=in(),w=in();

		E[i]=(node){u,v,w};

		f[u]=std::min(f[u],w+1);

		f[v]=std::min(f[v],w+2);

	}

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

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

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

	for(int i=0;i<n-1;++i)E[++tot]=(node){i,i+1,f[i]};

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

	std::sort(E+1,E+tot+1);

	ll mst=0;int cnt=1;

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

	for(int i=1;i<=tot&&cnt<n;++i)

	{

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

		if(u==v)continue;++cnt;fa[u]=v;mst+=E[i].w;

	}

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

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAX 200200

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

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

	return t?-x:x;

}

struct Line{int u,v,w;}e[MAX<<1];

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

int n,Q,m,v[MAX],f[MAX];long long ans=0;

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

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[m+1]);

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

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

	{

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

		if(u==v)continue;

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

	}

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

	return 0;

}


// Optimized solution to the same problem (faster):
#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gt getchar()

#define ll long long

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

typedef std::pair<int,int> P;

#define mk std::make_pair

#define fr first

#define sc second

inline int in()

{

	int k=0;char ch=gt;bool p=1;

	while(ch<'-')ch=gt;if(ch=='-')ch=gt,p=0;

	while(ch>'-')k=k*10+ch-'0',ch=gt;

	return p?k:-k;

}

const int N=2e5+5;

int f[N],fa[N];

struct node{int u,v,w;}E[N<<2];

inline bool operator<(const node &a,const node &b){return a.w<b.w;}

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

int main()

{

	int n=in(),Q=in(),tot=Q;

	memset(f,0x3f,n<<2);

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

	{

		int u=in(),v=in(),w=in();

		E[i]=(node){u,v,w};

		f[u]=std::min(f[u],w+1);

		f[v]=std::min(f[v],w+2);

	}

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

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

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

	for(int i=0;i<n-1;++i)E[++tot]=(node){i,i+1,f[i]};

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

	std::sort(E+1,E+tot+1);

	ll mst=0;int cnt=1;

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

	for(int i=1;i<=tot&&cnt<n;++i)

	{

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

		if(u==v)continue;++cnt;fa[u]=v;mst+=E[i].w;

	}

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

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define LL long long

#define db long double

#define il inline

#define re register

#define mkpr make_pair



using namespace std;

const int N=500000+10;

il int rd()

{

    int x=0,w=1;char ch=0;

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

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

/*int to[N<<1],nt[N<<1],w[N<<1],hd[N],tot=1;

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

{

	++tot,to[tot]=y,nt[tot]=hd[x],w[tot]=z,hd[x]=tot;

	++tot,to[tot]=x,nt[tot]=hd[y],w[tot]=z,hd[y]=tot;

}*/

int n,m,q,ff[N],w[N];

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

struct edge

{

	int x,y,z;

	bool operator < (const edge &bb) const {return z<bb.z;}

}e[N],ee[N];



int main()

{

	n=rd(),q=rd();

	for(int i=1;i<=n;++i) ff[i]=i,w[i]=1<<30;

	while(q--)

	{

		int x=rd()+1,y=rd()+1,z=rd();

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

		w[x]=min(w[x],z+1),w[y]=min(w[y],z+2);

	}

	int ii=1;

	for(int i=2;i<=n;++i) if(w[i]<w[ii]) ii=i;

	for(int i=ii,j=ii%n+1;j!=ii;i=i%n+1,j=j%n+1) w[j]=min(w[j],w[i]+2);

	for(int i=1;i<n;++i) e[++m]=(edge){i,i+1,w[i]};

	e[++m]=(edge){n,1,w[n]};

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

	LL ans=0;

	for(int i=1,j=n-1;i<=m&&j;++i)

		if(findf(e[i].x)!=findf(e[i].y)) --j,ans+=e[i].z,ff[findf(e[i].x)]=findf(e[i].y);

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

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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);

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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());

}

// Optimized solution to the same problem (faster):
#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;

}






















// Fastest known solution for this problem: