#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义边的结构体：两个顶点u、v和权重w
struct Edge {
    int u; // 顶点1
    int v; // 顶点2
    int w; // 边的权重（成本）
    
    // 重载小于号，用于按权重排序
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

// 并查集类，用于判断两个顶点是否连通以及合并
class UnionFind {
public:
    // parent数组：每个顶点的父节点（初始为自身）
    // rank数组：树的高度（用于按秩合并）
    vector<int> parent, rank;
    
    // 构造函数：初始化n个顶点，每个顶点独立
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i; // 初始父节点是自己
        }
    }
    
    // 查找顶点x的根节点（族长），并路径压缩
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 递归查找并压缩
        }
        return parent[x];
    }
    
    // 合并两个顶点所在的集合，成功返回true，已连通返回false
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false; // 已经在同一集合，无需合并
        
        // 按秩合并：把矮的树挂到高的树下
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            // 高度相同，随便挂一个，并增加高度
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
};

// Kruskal算法主函数，返回最小生成树的总权重
int kruskal(int n, vector<Edge> &edges) {
    // 第一步：按权重从小到大排序所有边
    sort(edges.begin(), edges.end());
    
    // 创建并查集，初始有n个独立的顶点
    UnionFind uf(n);
    
    int totalWeight = 0; // 总成本
    int count = 0;       // 已选中的边数
    
    // 遍历每一条边
    for (Edge &e : edges) {
        // 如果合并成功（两个顶点原本不连通）
        if (uf.unite(e.u, e.v)) {
            totalWeight += e.w; // 加上这条边的权重
            count++;            // 边数加1
            // 当已选边数达到n-1时，就可以提前结束
            if (count == n - 1) break;
        }
        // 如果合并失败，说明这条边会形成环，直接跳过
    }
    
    // 如果图不连通（比如有些顶点无法到达），count可能小于n-1，
    // 但题目保证图连通，所以这里直接返回总权重
    return totalWeight;
}

int main() {
    // 例子：5个村庄（编号0~4），6条路
    int n = 5; // 顶点数量
    vector<Edge> edges = {
        {0, 1, 2},  // 村庄0和1修路需2万元
        {0, 3, 6},  // 村庄0和3修路需6万元
        {1, 2, 3},  // 村庄1和2修路需3万元
        {1, 3, 8},  // 村庄1和3修路需8万元
        {1, 4, 5},  // 村庄1和4修路需5万元
        {2, 4, 7}   // 村庄2和4修路需7万元
    };
    
    int result = kruskal(n, edges);
    cout << "最小生成树的总成本: " << result << "万元" << endl;
    // 运行结果：选中的边为(0,1,2),(1,2,3),(1,4,5),(0,3,6) → 总成本2+3+5+6=16万元
    return 0;
}