#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <fstream>
#include <string.h>
using namespace std;

int main()
{
	using namespace boost;
	typedef adjacency_list < vecS, vecS, undirectedS,
    	property<vertex_distance_t, long>, property < edge_weight_t, int > > Graph;
	typedef std::pair < long, long >E;

	//read graph data from file
	long num_nodes,num_edges,u,v;
	int w;
	ifstream infile;
	infile.open("convertResult.txt");
	if(!infile)
	{
		 cerr<<"error:unable to open file."<<endl;
		 return -1;
	}
	infile>>num_nodes>>num_edges;
	E edges[num_edges];
	int weights[num_edges];
	for(long i=0;i<num_edges;i++)
	{
		infile>>u>>v>>w;
		edges[i] = make_pair(u,v);
		weights[i] = w;
	}	
  
	//construct input parameters
	Graph g(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes);
	property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);
	std::vector < graph_traits < Graph >::vertex_descriptor >
    p(num_vertices(g));

	//call the BGL PRIM
	prim_minimum_spanning_tree(g, &p[0]);

	//output the result
	ofstream outfile;
	outfile.open("primResult.txt");
	for (std::size_t i = 0; i != p.size(); ++i)
		if (p[i] != i)
			outfile<< "parent[" << i << "] = " << p[i] << std::endl;
		else
			outfile<< "parent[" << i << "] = no parent" << std::endl;

	return EXIT_SUCCESS;
}