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;
	bool operator<(const edge &e)const{ return cost<e.cost; }
};

vector<edge> Kruskal(int n,vector<edge> E){ // n = |V|, グラフは辺集合で与える
	vector<edge> M;
	sort(E.begin(),E.end());

	union_find U(n);
	for(int i=0;i<E.size();i++){
		int u=E[i].u,v=E[i].v;
		if(U.find(u)!=U.find(v)){
			U.unite(u,v);
			M.push_back(E[i]);
		}
	}
	return M;
}