#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct edge{
int x,y;
ll z;
} gs[400400];
int n,m;
ll ans;
ll best[200200];
int p[200200];
int par(int x){
return (p[x]==x)?x:(p[x]=par(p[x]));
}
int main(){
scanf("%d%d",&n,&m);
memset(best,0x7f,sizeof best);
for (int i=0;i<n;++i)
p[i]=i;
for (int i=0;i<m;++i){
static int x,y;
static ll z;
scanf("%d%d%lld",&x,&y,&z);
gs[i]=(edge){x,y,z};
best[x]=min(best[x],z+1);
best[y]=min(best[y],z+2);
}
for (int it=0;it<2;++it)
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)
gs[m+i]=(edge){i,(i+1)%n,best[i]};
sort(gs,gs+m+n,[](const edge &a,const edge &b){return a.z<b.z;});
for (int i=0;i<m+n;++i){
int fa=par(gs[i].x);
int fb=par(gs[i].y);
if (fa!=fb){
ans+=gs[i].z;
p[fa]=fb;
}
}
printf("%lld\n", ans);
}
./Main.cpp: In function ‘int main()’:
./Main.cpp:18:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
./Main.cpp:26:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld",&x,&y,&z);
^