#include #include #include using namespace std; struct UnionFind { vector parent; UnionFind(int n) { parent.assign(n, -1); } int root(int x) { return parent[x] < 0 ? x : (parent[x] = root(parent[x])); } void unite(int x, int y) { x = root(x); y = root(y); if (x == y) return; if (parent[x] > parent[y]) swap(x, y); parent[x] += parent[y]; parent[y] = x; } bool equiv(int x, int y) { return root(x) == root(y); } }; struct Edge { int u, v; long cost; bool operator < (Edge const& o) { return cost < o.cost; } }; long kruskal(int N, vector &edges, UnionFind uf) { vector mintree_edges; //UnionFind uf(N); long cost=0; sort(edges.begin(), edges.end()); for (Edge &e : edges) { if (uf.equiv(e.u, e.v)) continue; uf.unite(e.u, e.v); //mintree_edges.push_back(e); cost+=e.cost; } return cost; //return mintree_edges; } int main() { int N, M, K; cin >> N >> M >> K; vector edges; long ans=0; for (int i=0;i> a >> b >> c; --a;--b; Edge e; e.u=a; e.v=b; e.cost=c; edges.push_back(e); ans += c; } UnionFind uf(N); for (int i=0;i> e; --e; uf.unite(edges[e].u, edges[e].v); ans -= edges[e].cost; } ans -= kruskal(N, edges, uf); cout << ans << endl; }