#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_N = 200000; vector _parent; vector _rank; vector _size; class UnionFind { public: UnionFind(int n) { for (int i = 0; i < n; ++i) { _parent.push_back(i); _rank.push_back(0); _size.push_back(1); } } int find(int x) { if (_parent[x] == x) { return x; } else { return _parent[x] = find(_parent[x]); } } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (_rank[x] < _rank[y]) { _parent[x] = y; _size[y] += _size[x]; } else { _parent[y] = x; _size[x] += _size[y]; if (_rank[x] == _rank[y]) ++_rank[x]; } } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return _size[find(x)]; } }; struct Edge { int from; int to; int cost; Edge(int from = -1, int to = -1, int cost = -1) { this->from = from; this->to = to; this->cost = cost; } bool operator>(const Edge &e) const { return cost > e.cost; } }; int main() { int N, M; cin >> N >> M; priority_queue , greater> pque; for (int i = 0; i < M; ++i) { int a, b, w; cin >> a >> b >> w; pque.push(Edge(a, b, w)); } ll ans = 0; UnionFind uf(N + 1); while (not pque.empty()) { Edge e = pque.top(); pque.pop(); if (uf.same(e.from, e.to)) continue; int size = uf.size(e.from) + uf.size(e.to); if (uf.size(e.from) == 1 || uf.size(e.to) == 1) { --size; } uf.unite(e.from, e.to); ans += size * e.cost; } cout << ans << endl; return 0; }