class union_find{
	vector<int> p,rank;
public:
	union_find(int n):p(n),rank(n){
		for(int x=0;x<n;x++) p[x]=x;
	}
	int find(int x){
		if(x!=p[x]) p[x]=find(p[x]);
		return p[x];
	}
	void unite(int x,int y){ // union は C++ の予約語なので unite で代用
		x=find(x);
		y=find(y);
		if(rank[x]> rank[y]) swap(x,y);
		if(rank[x]==rank[y]) rank[y]++;
		p[x]=y;
	}
};

struct edge{
	int u,v;
	double cost;
};

typedef vector< vector<edge> > graph;

vector<edge> Boruvka(graph G){ // グラフは隣接リストで与える
	int n=G.size(); // n = |V|
	graph M(n); // MST は隣接リストの形で求める

	union_find U(n);
	while(true){
		vector<edge> F; // このフェイズで M に追加する辺 ( の候補 )

		int c=0;
		vector<int> id(n,-1); // 連結成分の名前 ( 未割り当てなら -1 )
		for(int u=0;u<n;u++) if(id[u]==-1) {
			id[u]=c;

			// 頂点 u を含む M の連結成分 C を求める
			vector<int> C;
			queue<int> Q; Q.push(u);
			while(!Q.empty()){
				int v=Q.front(); Q.pop();

				C.push_back(v);

				for(int i=0;i<M[v].size();i++){
					edge e=M[v][i];
					if(id[e.v]==-1){
						id[e.v]=c;
						Q.push(e.v);
					}
				}
			}

			c++;

			// C から出る重み最小の辺 e を求める
			edge e={-1,-1,-1};
			for(int i=0;i<C.size();i++){
				int v=C[i];
				for(int j=0;j<G[v].size();j++){
					edge f=G[v][j];
					if(id[f.v]!=id[u]){
						if(e.u==-1 || e.cost>f.cost) e=f;
					}
				}
			}
			if(e.u!=-1) F.push_back(e);
		}

		if(c==1) break; // 連結成分が一つだけなら終了

		// M に F の辺を追加する
		for(int i=0;i<F.size();i++){
			edge e=F[i];
			if(U.find(e.u)!=U.find(e.v)){
				U.unite(e.u,e.v);
				M[e.u].push_back(e);
				swap(e.u,e.v);
				M[e.u].push_back(e);
			}
		}
	}

	return M;
}