#include <iostream>
#include <string.h>
#define INT_MAX 1000000000
using namespace std;

int matrix[100][100];//邻接矩阵
bool visited[100];//标记数组
int path[100];//记录生成树路径
int lowcost[100];//边的权值
int vertex_num,arc_num;//顶点数，弧数
int sum;//权值总和
int source;//源点
void prim(int source);
int main()
{
    cout << "请输入图的顶点数（<=100）：";
    cin >> vertex_num;
    cout << "请输入图的弧数：";
    cin >> arc_num;

    for (int i = 0; i < vertex_num; i++)
        for (int j = 0; j < vertex_num; j++)
            matrix[i][j] = INT_MAX;  //初始化matrix数组

    cout << "请输入弧的信息：\n";
    int u, v, w;
    for (int i = 0; i < arc_num; i++)
    {
        cin >> u >> v >> w;
        matrix[u][v] = matrix[v][u] = w;
    }

    cout << "请输入起点（<" << vertex_num << "）：";
    cin >> source;
    prim(source);

    cout << "最小生成树权和为：" << sum << endl;
    cout << "最小生成树路径为：\n";
    for (int i = 0; i < vertex_num; i++)
        if (i != source)
            cout << i << "----" << path[i] << endl;

    return 0;
}
void prim(int source){
    memset(visited,0,sizeof(visited));
    visited[source]=true;
    for(int i=0;i<vertex_num;i++){
        lowcost[i] = matrix[source][i];
        path[i]=source;
    }

    int min_cost,min_cost_index;//最小的权值，和其下标
    sum=0;
    for(int i=1;i<vertex_num;i++){//找除源点外的n-1个点,如果这里写多了，
                                //那么下边的for里if进不去，那么sum的值也会错误
            min_cost=INT_MAX;

        for(int j=0;j<vertex_num;j++){//遍历所有顶点
            if(visited[j]==false&&lowcost[j]<min_cost){//找到与源点的权值最小的点
                min_cost=lowcost[j];
                min_cost_index=j;
            }
        }
        visited[min_cost_index]=true;//讲找到的顶点进行标记
        sum+=min_cost;//权值总和

        for(int j=0;j<vertex_num;j++){
            if(visited[j]==false&&matrix[min_cost_index][j]<lowcost[j]){//更新lowcost，以便找下个顶点
                lowcost[j]=matrix[min_cost_index][j];
                path[j] = min_cost_index;
            }
        }
    }


}

#include <iostream>
#include <algorithm>
#define MAX_INT 100
using namespace std;
struct Edge{//边
int a;//边上的两个点
int b;
int weight;//权值
}edge[MAX_INT];
int par[MAX_INT];//i的父亲的编号
int rank[MAX_INT];//i的高度
void init(int n);//初始化
int find(int x);//查找根节点并且压缩路径
bool  unite(int x,int y);//合并
bool compare(const Edge&a,const Edge&b);
int vertex_num,arc_num;//顶点数，弧数
int case_num;//测试组数
int sum;//权值总和
int main()
{
    cout<<"请输入测试组数："<<endl;
    cin>>case_num;
    while(case_num){
        sum=0;
        cout<<"请输入顶点数和弧数:"<<endl;
        cin>>vertex_num>>arc_num;

        init(vertex_num);

        cout<<"请输入"<<arc_num<<"条弧的信息："<<endl;
        for(int i=0;i<arc_num;i++){
            cin>>edge[i].a>>edge[i].b>>edge[i].weight;
            }

        sort(edge,edge+arc_num,compare);

        cout<<"最小生成树的路径为:"<<endl;
        int j;
        for(j=0;j<arc_num;j++){
            if(unite(edge[j].a,edge[j].b)){
                sum+=edge[j].weight;
                cout<<edge[j].a<<"----"<<edge[j].b<<" "<<edge[j].weight<<endl;
        }
        }
        if(j==arc_num){
            cout<<"最小生成树的权值和为："<<sum<<endl;
        }else if(j<arc_num){
            cout<<"data error!"<<endl;
        }

        case_num--;
    }
    return 0;
}
void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;//父节点都先初始化为自己
        rank[i]=0;//高度初始化为0
    }

}

int find(int x){
if(x==par[x]){
    return x;
}else{
    return par[x]=find(par[x]);
}
}
bool  unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y){
        return false;
    }else{
    if(rank[x]<rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rank[x]==rank[y])
            rank[x]++;
    }
    return true;
    }

}

bool compare(const Edge&a,const Edge&b){//按从小到大的顺序排序
    return a.weight<b.weight;
}