Demolition of Bridges (AOJ 0180) by mzsrkn10
Contest: 3575    RunID: 2376297    Status: Accepted    Date: Sat Jun 17 17:03:26 JST 2017


#include<bits/stdc++.h>

#define MAX_E 501
#define MAX_V 101
#define INF 1e9

using namespace std;

int cost[MAX_V][MAX_V]; // cost[u][v]は辺e=(u,v)のコスト(存在しない場合はINF)
int mincost[MAX_V]; // 集合Xからの辺の最小コスト
bool used[MAX_V];   // 頂点iがXに含まれているか
int V;

int prim() {
  for (int i = 0; i < V; ++i) {
    mincost[i] = INF;
    used[i] = false;
  }
  mincost[0] = 0;
  int res = 0;

  while (true) {
    int v = -1;
    // Xに属さない頂点のうちXからの辺のコストが最小になる頂点を探す
    for (int u = 0; u < V; u++) {
      if (!used[u] && (v == -1 || mincost[u] < mincost[v]))
        v = u;
    }

    if (v == -1)
      break;
    used[v] = true;    // 頂点vをXに追加
    res += mincost[v]; // 辺のコストを加える

    for (int u = 0; u < V; u++) {
      mincost[u] = min(mincost[u], cost[v][u]);
    }
  }

  return res;
}

int main(){
    int n, m;
    while(cin >> n >> m, n != 0 || m != 0){
        V = n;
        for(int i=0;i<MAX_V;++i)
            for(int j=0;j<MAX_V;++j)
                cost[i][j] = INF;
        for(int i=0;i<m;++i){
            int a, b, c;
            cin >> a >> b >> c;
            cost[a][b] = c;
            cost[b][a] = c;
        }
        cout << prim() << endl;
    }

    return 0;
}