#pragma GCC optimize("Ofast,no-stack-protector") #include <algorithm> #include <cstdlib> #include <iostream> #include <numeric> #include <tuple> #include <utility> #include <vector> using namespace std; using i64 = long long; inline i64 cube(int x) { return (i64)x * x * x; } inline i64 get_cost(const pair<int, int>& u, const pair<int, int>& v) { int ux = u.first, uy = u.second, vx = v.first, vy = v.second; return cube(abs(ux - vx)) + cube(abs(uy - vy)); } struct DSU { int n; vector<int> fa, siz; DSU(int n) : n(n) , fa(n) , siz(n, 1) { iota(fa.begin(), fa.end(), 0); } int find(int u) { return u == fa[u] ? fa[u] : fa[u] = find(fa[u]); } bool same(int u, int v) { return find(u) == find(v); } void merge(int u, int v) { u = find(u); v = find(v); if (siz[u] < siz[v]) swap(u, v); siz[u] += siz[v]; fa[v] = u; } void clear() { siz.assign(n, 1); iota(fa.begin(), fa.end(), 0); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, q; cin >> n >> q; vector<pair<int, int>> nodes(n); for (auto& node : nodes) cin >> node.first >> node.second; vector<vector<i64>> weight(n); vector<int> idx; idx.reserve(5 + (n * (n - 1) >> 1)); for (int i = 0; i < n; ++i) { weight[i].resize(i); for (int j = 0; j < i; ++j) { weight[i][j] = get_cost(nodes[i], nodes[j]); idx.emplace_back(i * n + j); } } i64 ans = 0; int cnt = 0; DSU uf(n); vector<tuple<i64, int, int, int>> edges; sort(idx.begin(), idx.end(), [&](int lhs, int rhs) { return weight[lhs / n][lhs % n] < weight[rhs / n][rhs % n]; }); for (auto edge : idx) { if (cnt >= n - 1) break; int u = edge / n, v = edge % n; i64 w = weight[u][v]; if (!uf.same(u, v)) { uf.merge(u, v); edges.emplace_back(w, u, v, -1); ans += w; ++cnt; } } cout << ans << '\n'; for (int i = 0; i < q; ++i) { int u, v; i64 w; scanf("%d %d %lld", &u, &v, &w); edges.emplace_back(w, --u, --v, i); } auto get_mst = [&](int lim) { ans = cnt = 0; uf.clear(); for (const auto& edge : edges) { if (cnt >= n - 1) break; else if (get<3>(edge) > lim) continue; int u = get<1>(edge), v = get<2>(edge); if (!uf.same(u, v)) { uf.merge(u, v); ++cnt; ans += get<0>(edge); } } cout << ans << '\n'; }; sort(edges.begin(), edges.end()); for (int i = 0; i < q; ++i) get_mst(i); return 0; }