【问题描述】
 已知含有n个顶点的带权连通无向图，采用邻接矩阵存储，邻接矩阵以三元组的形式给出，只给出不包括主对角线元素在内的下三角形部分的元素，且不包括不相邻的顶点对。求该连通图的最小生成树中各边的权值之和。
 注：三元组来表一条带权的边，如2 1 7表示顶点2到顶点1的边的权值为7.
【输入形式】
 第一行给出结点个数n和三元组的个数count，以下每行给出一个三元组，数之间用空格隔开。（注意这里顶点的序号是从1到n，而不是0到n-1，程序里要小心！）

【输出形式】
 最小生成树的权值

【样例输入】
 5 8
 2 1 7
 3 1 6
 3 2 8
 4 1 9
 4 2 4
 4 3 6
 5 2 4
 5 4 2

【样例输出】
 18

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 200010;
int n,m;
int p[N];

struct Edge{
    int a,b,w;
    bool operator<(const Edge &W)const
    {
        return w < W.w;
    }
}edges[N];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}


int main(){
    scanf("%d%d", &n, &m);

    for(int i = 0;i < m;i ++){
        int a,b,w;
        scanf("%d%d%d", &a, &b,&w);
        edges[i]={a,b,w};
    }
    sort(edges,edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int res = 0,cnt = 0;
    for (int i = 0; i < m; i ++ ){
        int a=edges[i].a, b=edges[i].b, w=edges[i].w;
        a = find(a), b = find(b);
        if(a != b){
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
    if(cnt < n-1) puts("impossible");
    else printf("%d\n",res);

    return 0;
}