#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int MX = 210000;
const int MAXN = 210000;
int n, q;
set<pair<int, int> > ss0;
set<pair<int, int> > ss1;
set<pair<int, int> > ss2;
int a[MAXN];
int b[MAXN];
ll c[MAXN];
vector<pair<int, int> > go[MX];
int p[MAXN];
int sz[MAXN];
int get(int a) {
if (a == p[a])
return a;
return p[a] = get(p[a]);
}
int un(int a, int b) {
a = get(a);
b = get(b);
if (a == b)
return 0;
if (sz[a] < sz[b])
swap(a, b);
sz[a] += sz[b];
p[b] = a;
return 1;
}
int main() {
scanf("%d%d", &n, &q);
ll mn = 1e9;
for (int i = 0; i < q; ++i) {
scanf("%d%d%lld", a + i, b + i, c + i);
mn = min(mn, c[i]);
}
ll ans = mn * (n - 1);
for (int i = 0; i < q; ++i)
c[i] -= mn;
for (int i = 0; i < q; ++i) {
if (c[i] < MX)
go[c[i]].push_back(make_pair(a[i], b[i]));
if (c[i] + 1 < MX) {
go[c[i] + 1].push_back(make_pair((a[i] + 1) % n, b[i]));
}
}
for (int i = 0; i < n; ++i)
p[i] = i, sz[i] = 1;
for (int i = 0; i < MX; ++i) {
for (auto j: go[i])
ss0.insert(j);
ss2.clear();
for (auto j: ss0) {
if (un(j.first, j.second))
ss2.insert(make_pair((j.first + 1) % n, (j.second + 1) % n)), ans += i;
}
swap(ss0, ss2);
swap(ss1, ss0);
}
cout << ans << "\n";
return 0;
}
./Main.cpp: In function ‘int main()’:
./Main.cpp:56:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q);
^
./Main.cpp:59:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", a + i, b + i, c + i);
^