Demolition of Bridges (AOJ 0180) by letter
Contest: 3575    RunID: 2376321    Status: Accepted    Date: Sat Jun 17 17:22:27 JST 2017


#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
 
typedef long long ll;
typedef pair<int, int> ii;

#define DEBUG false

struct UnionFind {
  vector<int> data;
  UnionFind(int v) : data(v, -1) {}
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -data[root(x)];
  }
  void merge(int x, int y) {
    x = root(x), y = root(y);
    if (x != y) {
      if (size(y) > size(x))
        swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }
};

struct NODE{
	int x, y;
	int cost;
	
	NODE(){x = y = cost = 0;}
	NODE(int x, int y, int cost):x(x), y(y), cost(cost){}
	
	bool operator<(const NODE r){
		return cost < r.cost;
	}
};

int main(){
	
	int n, m;
	while(cin >> n >> m, m, n){
		vector<NODE> v(m);
		rep(i, m){
			int x, y, cost;
			cin >> x >> y >> cost;
			v[i] = NODE(x, y, cost);
		}
		
		SORT(v);
		
		UnionFind uni(n+1);
		
		ll ans = 0;
		rep(i, m){
			int xx = v[i].x;
			int yy = v[i].y;
			if(uni.root(xx) != uni.root(yy)){
				uni.merge(xx, yy);
				ans += v[i].cost;
			}
		}
		
		cout << ans << endl;
		
	}
	
	
	
	return 0;
}

/*
struct BIT {
  int N;
  vector<ll> data;
  BIT(int n) : N(n), data(n + 1, 0) { }
  void add(int a, ll w) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x] += w;
    }
  }
  ll sum(int a) {
    ll ret = 0;
    for(int x = a; x > 0; x -= x & -x) {
      ret += data[x];
    }
    return ret;
  }
  
  ll sum(int l, int r){//[l, r)
  	return sum(r) - sum(l);
  }
};

BIT bit = BIT(1);
int m, n;

ll dfs(int pos, int rest){
	ll ret = LLINF;
	
	if(rest == 1) return bit.sum(pos, n+1);
	for(int i = 0; i + pos <= n+1; i++){
		ll hoge1 = bit.sum(pos, pos+i);
		ll hoge2 = dfs(pos+i, rest-1);
		cout << "sum(" << pos << ", " << pos+i << "): " << hoge1 << endl;
		cout << "des(" << pos+i << ". " << rest-1 << "): " << hoge2 << endl;
		cout << endl;
		ret = min(ret, hoge1 + hoge2);
	}
	
	return ret;
}

int main(){

	while(cin >> m >> n, m, n){
		bit = BIT(n);
		rep(i, n){
			ll tmp;
			cin >> tmp;
			bit.add(i+1, tmp);
		}
		
		cout << dfs(1, m) << endl;
		
	}
	
	return 0;
}
*/