#include <iostream>
#include <vector>
using namespace std;

// 3ICE: Globals holding vertex and edge count, because I'm too lazy to pass them around.
int vertex_count, edge_count;

#define visited true
#define not_visited false
vector<bool> visited_status; // 3ICE: Status: true if visited, false otherwise.

vector<vector<int> > w; // 3ICE: Weight matrix

vector<int> calculated_cost;

vector<int> connected_to;

// 3ICE: Forward declaring the algorithm so it can be placed below main.
void prim();

int main(){
	cout<<"Prim's Algorithm implemented by Daniel \"3ICE\" Berezvai.\n\n";

	cout<<"Number of vertices: V=";
	cin>>vertex_count;

	cout<<"Number of edges: E=";
	cin>>edge_count;

// 3ICE: Initialize all the vectors
	w.resize(vertex_count);
	visited_status.resize(vertex_count);
	calculated_cost.resize(vertex_count);
	connected_to.resize(vertex_count);
#define maximum_cost 32767
	for(int i=0;i<vertex_count;i++){
		w[i].resize(vertex_count);
		for(int j=0;j<vertex_count;j++){
			w[i][j]=maximum_cost;
		}
		connected_to[i]=i;
		visited_status[i]=not_visited;
		calculated_cost[i]=maximum_cost;
	}

	int a, b, weight;
	for(int i=0;i<edge_count;i++){
		cout<<"Edge #"<<i+1<<": Enter the two connected vertex IDs and the weight: (a, b, w)=";
		cin>>a>>b>>weight;
		a-=1; // 3ICE: Human to computer translation
		b-=1; // 3ICE: (For example users think the first vertex ID is #1 but programmers prefer to use #0.)
		w[a][b]=w[b][a]=weight;
	}

	prim();
	return 0;
}

void prim(){
	int m; // 3ICE: Minimum cost
	int t=1; // 3ICE: Total visited
	int c=0; // 3ICE: Current
	calculated_cost[0]=0;
	visited_status[0]=visited;
	while(t!=vertex_count){ // 3ICE: We must visit every vertex.
		for(int i=0;i<vertex_count;i++){ // 3ICE: Loop through all vertices looking for the best
			if(w[c][i]!=maximum_cost && !visited_status[i] && calculated_cost[i]>w[c][i]){ // 3ICE: If:
			// 3ICE: the weight of the edge connecting the two selected vertices isn't maximum_cost and
			// 3ICE: we haven't yet visited this vertex and
			// 3ICE: the weight is smaller than the best we found so far then
				calculated_cost[i]=w[c][i];
				connected_to[i]=c; // 3ICE: Record this as the new best vertex to connect to
			}
		}
		m=maximum_cost; // 3ICE: Initialize minimum cost to maximum possible integer value
		for(int i=0;i<vertex_count;i++){ // 3ICE: Loop through all vertices again
			if(!visited_status[i] && calculated_cost[i]<m){ // 3ICE: If the cost is minimal
			m=calculated_cost[i]; // 3ICE: Record minimum cost
			c=i;// 3ICE: Go to the new vertex
			}
		}
		visited_status[c]=visited; // 3ICE: Mark the new vertex as visited
		t++; // 3ICE: We have successfully visited one vertex.
	}

	m=0; // 3ICE: Reset the variable for reuse (Calculating the sum)

	cout<<"\n\nThe minimum cost spanning tree is as follows:\n";
	for(int i=0;i<vertex_count;i++){
		m+=calculated_cost[i];
		if(i!=connected_to[i] && calculated_cost[i]!=maximum_cost){ // 3ICE: We are not interested in the first vertex connecting to itself. ("Vertex #1 is connected to vertex #1 for a minimal cost of 0.")
			cout<<"Vertex #"<<i<<" is connected to vertex #"<<connected_to[i]<<" for a minimal cost of "<<calculated_cost[i]<<"\n";
		}
	}
		cout<<"The total cost was "<<m<<".";
}