#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <memory.h>

// Create the edge type
struct Edge
{
	int from;
	int to;
	int weight;
	bool inTheCut;
};
typedef Edge* pEdge;


// adjacency list
struct ListIt
{
	int value;
	ListIt *p_next;
};

// typedef for the pointer type
typedef ListIt* pListIt;

pEdge edges;
pEdge edgesPr;

int n,m;

int *tree;
int *ancient;
int **distanceMatrix;


pListIt* adjacencyList; // Here we save the relations.... A 100000 is the maximum vertexes


void read();
void print();
void Kruskal();
int Prim(int at);
bool add(pListIt &dest, int val);
int compareEdges(const void* el1, const void* el2);
int min_vag();

int main()
{
	read();
	printf("\n");
	print();

	//Kruskal();

	printf("\n\n With Prims Technique: \n\n");
	Prim(1);

	return 0;
}

//************************************
// Method:    read - public  access
// Returns:   void
//
// Purpose:   Read in the data from In.txt
//************************************
void read()
{
	FILE *f;
	freopen_s(&f, "In.txt", "r", stdin);
	freopen_s(&f, "Out.txt", "w", stdout);

	scanf_s("%d", &n);
	scanf_s("%d", &m);

	tree = (int*) calloc(n+1, sizeof(int));
	ancient = (int*) calloc(n+1, sizeof(int));
	edges = (pEdge)malloc(m*sizeof(Edge));
	adjacencyList = (pListIt*) calloc(n+1,sizeof(pListIt));

	distanceMatrix = (int**) calloc(n+1, sizeof(int*));
	for (int j = 1; j <=n; ++j)
	{
		distanceMatrix[j] = (int*) calloc(n+1, sizeof(int));
	}


	int from,to,distance;

	for(int i =0; i< m; ++i)
	{
		scanf_s("%d%d%d", &from, &to, & distance);

		add(adjacencyList[from], to);
		add(adjacencyList[to], from);

		edges[i].from = from;
		edges[i].to = to;
		edges[i].weight = distance;
	}
}

//************************************
// Method:    print - public  access
// Parameter:
// Returns:   void
//
// Purpose:   Print the list of edges
//************************************
void print()
{
	printf("\n The list of the edges:\n ");
	for(int i =0; i < m; ++i)
	{
		if(!(i % 1)) // how many in a row... for now 1 edge per row
		{
			printf("\n");
		}
		printf(" %d ~ %d -> %d   ", edges[i].from, edges[i].to, edges[i].weight);
	}

	printf("\n");

}

void Kruskal()
{
	int i = 0, overallWeight = 0 , j =0;
	int fromTree = 0, toTree = 0, changeNr = 0;


	// sort the edge list
	qsort((void*)edges,m,sizeof(Edge),compareEdges);


	printf("\n");
	print();
	printf("\n");

	printf("\nThe list of the edges with the algorithm of Kruskall:\n");


	// build up the individual list
	for ( i =1;  i <= n; ++i)
		tree[i] = i;


	for ( i= 0; i < m && changeNr < n; ++i)
	{
		fromTree = tree[edges[i].from];
		toTree = tree[edges[i].to];

		if( fromTree != toTree)
		{
			++changeNr;
			overallWeight += edges[i].weight;
			printf("   %d) %d ~ %d -> %d  \n", changeNr, edges[i].from, edges[i].to, edges[i].weight);

			//Union of the trees
			for ( j = 0; j < m; ++j)
				if(tree[j] == toTree)
					tree[j] = fromTree;
		}
	}
	printf( " \n The minimal weight %d ", overallWeight);

}

//************************************
// Method:    compareEdges - public  access
// Parameter:
//			  const void * edge1
//			  const void * edge2
// Returns:   int
//
// Purpose:   Compare two edge types according to their weight
//************************************
int compareEdges(const void* edge1, const void * edge2)
{
	pEdge first = (pEdge)edge1;
	pEdge second = (pEdge)edge2;

	return first->weight - second->weight;
}

//************************************
// Method:    Prim - public  access
// Parameter:
//			  int at
// Returns:   int
//
// Purpose:   Prims Technique to generate the minimal spanning tree
//************************************
int Prim(int at)
{
	int i = 0;

	memset(tree, 0, (n+1)*sizeof(int));

	tree[at] = 1;
	ancient[at]  = 0 ;


	// sort the edge list
	qsort((void*)edges,m,sizeof(Edge),compareEdges);


	// build up the tree
	for (i = 0; i < m; ++i)
	{
		distanceMatrix[edges[i].from][edges[i].to  ] = i;
		distanceMatrix[edges[i].to  ][edges[i].from] = i;

		if (edges[i].from == at || edges[i].to == at)
		{
			edges[i].inTheCut = true;
		}
		else
		{
			edges[i].inTheCut = false;
		}
	}

	int overallWeight = 0;
	int curent = 0;
	int addedVertex = 1;
	int neighborVertex = 0;
	int neighborEdge = 0;
	pListIt p = NULL;
	int j = 0;

	for(i = 1; i < n; ++i)
	{
		for ( j =0 ; j < m; ++j)
		{
			if (edges[j].inTheCut)
			{
				curent = j;
				break;
			}
		}


		printf( "   %d)  %d ~ %d -> %d \n",i, edges[curent].from,edges[curent].to, edges[curent].weight);

		overallWeight += edges[curent].weight;

		if (tree[edges[curent].from] == 1)
		{
			addedVertex = edges[curent].to;
			ancient[addedVertex] = edges[curent].from;
		}

		tree[addedVertex] = 1;

		for (p = adjacencyList[addedVertex]; p != NULL; p = p -> p_next)
		{
			neighborVertex = p->value;
			neighborEdge = distanceMatrix[addedVertex][neighborVertex];

			if (tree[neighborVertex] == 1)
				edges[neighborEdge].inTheCut = false; // reset if both ends are there
			else
				edges[neighborEdge].inTheCut = true; // set if only one is there

		}

	}

	printf( "\n\n The overall Weight: %d " , overallWeight);
	return 0;
}


// Here we need to make sure that the items are added in 	 // correct order
bool add(pListIt &dest, int val)
{
	//create the item
	pListIt p;
	p = (pListIt) malloc(sizeof(ListIt));
	p -> value = val;

	if(!dest)  // first item addition
	{
		p -> p_next = NULL;
		dest = p;
	}
	else
	{
		pListIt find = dest;
		pListIt at = NULL;

		// first find the first greater number, insert before
		while(find && find->value <= val)
		{
			if( find->value == val) // do not add a duplicate
			{
				free(p);
				return false;
			}

			at = find;
			find = find->p_next;
		}

		// insert at
		if (at) // insert at a valid point
		{
			p->p_next = at->p_next;
			at->p_next = p;
		}
		else // insert at the start
		{
			p->p_next = dest;
			dest = p;
		}
	}

	return true;
	_getch();
}