class MST	
{
	Graph<int,int> *pg;			
	void Prim(int v);
public:
	vector<Edge<int> > mstEdges;
	bool f;						
	int mstW;					
	int v;						
public:
	MST(Graph<int,int> *g);
	Graph<int,int> *GetGraph()
	{
		return pg;
	}
 
 
};
 
 
MST::MST(Graph<int,int> *g):
pg(g),f(false),mstW(0)
{
}
 
void MST::Prim(int _v)
{
	const int INF = INT_MAX;
	int vNum = pg->GetVertices();
	PrtQueue<int> Q(vNum);		
	vector<int> p(vNum,-1);		
	mstEdges.clear();		
	mstW = 0;
	for (int i=0;i<vNum;i++)
		Q.Enq(i,INF);	
	Q.RePrt(_v,0);		
	while (!Q.IsEmp())	
	{
		int u; 
		int prt;
		Q.Deq(u,prt);	
 
		if (p[u] != -1)	
		{
			int w = 0;
			try
			{
				mstEdges.push_back(Edge<int>(p[u],u, w=pg->GetEdgeWeight(p[u],u)));
			} catch(int e) {}
			mstW += w;	
		}
		Graph<int,int>::Iterator it(pg,u);
		for(int v=it.Begin();!it.Off();v=it.Next())
		{
 
			int w=*it; 
			bool r=Q.IsMem(it.vertex());
			if (Q.IsMem(it.vertex()) || *it<Q.GetPrt(it.vertex()))
			{	
				p[v] = u;
				Q.RePrt(v,*it);
			}
		}
		if(it.Begin()==-1)
			return;
	}
}
bool MST::operator ()(int _v)
{
	v = _v;
	if(!pg->weighted() || pg->directed())
	{
		f = false;
		return f;
	}
	Prim(v);
	f = true;
	return f;
}