struct edge{
	int u,v;
	double cost;
	bool operator<(const edge &e)const{ return cost>e.cost; } // C++ の priority_queue が max heap なので, つじつまを合わせるために順序を逆にする
};

typedef vector< vector<edge> > graph;

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

	vector<bool> H(n);

	priority_queue<edge> Q;
	Q.push((edge){-1,0,0}); // u0=0 と選んだ. -1 はダミ－
	while(M.size()<n-1){
		edge e=Q.top(); Q.pop();

		if(e.u!=-1) M.push_back(e); // 最初の一回以外は M に追加

		for(int i=0;i<G[e.v].size();i++){
			edge f=G[e.v][i];
			if(!H[f.v]) Q.push(f);
		}
	}

	return M;
}