#include <iostream> #include <cstring> #include <cstdio> using namespace std; #define INF 0x3f3f3f3f #define MAXN 105 bool visit[MAXN]; //标记数字是否放入一个集合 int lowc[MAXN]; //维护的最低代价数组 int cost[MAXN][MAXN]; //边的的权值 int Prim(int n){ int ans = 0; visit[1] = true; for(int i = 2; i <= n; i++){ lowc[i] = cost[1][i]; } for(int i = 1; i < n; i++){ //将剩余的n-1个点放入visit int minc = INF; int p = 0; for(int j = 2; j <= n; j++){ //查找一个没有放入visit的且权值最小的顶点 if(!visit[j] && minc > lowc[j]){ minc = lowc[j]; p = j; } } if(minc == INF) //这是一个不连通图,所以无最小生成树 return -1; ans += minc; visit[p] = true; for(int i = 2; i <= n; i++){ //更新维护顶点到visit集合的最小消耗 if(lowc[i] > cost[p][i]){ lowc[i] = cost[p][i]; } } } return ans; } int main(){ int n, m; //顶点,边数 while(scanf("%d%d", &n, &m) == 2){ memset(cost, INF, sizeof(cost)); int u, v, w; for(int i = 1; i <= m; i++){ scanf("%d%d%d", &u, &v, &w); cost[u][v] = w; cost[v][u] = w; } printf("%d ", Prim(n)); } return 0; }