#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;
}
./Main.cpp: In function ‘int main()’:
./Main.cpp:19:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&n,&m);
^
./Main.cpp:26:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&a,&b,&c);
^