#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LINE_LENGTH 200
#define MAXNUM 10000
#define MAXXX 1000000

struct ListNode {
	int key;
	struct ListNode* next;
};

struct FibNode {
	double key;
	int nodeNum; // stores which node this value belongs to
	int marked; // 0 means unmarked; 1 means marked
	int rang; // number of childs
	struct FibNode* parent;
	struct FibListNode* childs;
};

struct FibListNode {
	struct FibNode* key;
	struct FibListNode* next;
};

struct DListNode {
	struct FibNode* root;
	struct DListNode* next;
	struct DListNode* prev;
};

struct DListNode* Fib_Heap;

struct FibNode* insertFib(double n, int nodeNum) {
	if (Fib_Heap->root == NULL) {

		struct FibNode* first = (struct FibNode*) malloc(sizeof(struct FibNode));
		first->childs = NULL;
		first->parent = NULL;
		first->nodeNum = nodeNum;
		first->marked = 0;
		first->rang = 0;
		first->key = n;

		Fib_Heap->root = first;
		Fib_Heap->next = Fib_Heap;
		Fib_Heap->prev = Fib_Heap;
		return first;
	}
	else {
		struct FibNode* in = (struct FibNode*) malloc(sizeof(struct FibNode));
		in->nodeNum = nodeNum;
		in->marked = 0;
		in->key = n;

		if (n < Fib_Heap->root->key) {
			Fib_Heap->root->parent = in;
			in->parent = NULL;

			struct FibListNode* child = (struct FibListNode*) malloc(sizeof(struct FibListNode));
			child->next = NULL;
			child->key = Fib_Heap->root;
			in->childs = child;

			Fib_Heap->root = in;
			Fib_Heap->root->rang = 1;
		}
		else {
			in->parent = Fib_Heap->root;
			in->childs = NULL;
			in->rang = 0;

			struct FibListNode* child = (struct FibListNode*) malloc(sizeof(struct FibListNode));
			child->key = in;

			if (in->parent->rang == 0) {
				child->next = NULL;
				in->parent->childs = child;
				in->parent->rang = 1;
			}
			else {
				child->next = in->parent->childs;
				in->parent->childs = child;
				in->parent->rang++;
			}

		}
		return in;
	}
}

double getMin() {
	return Fib_Heap->root->key;
}

int getMinIndex() {
	return Fib_Heap->root->nodeNum;
}

int deleteMin() {
	struct FibListNode* temp = Fib_Heap->root->childs;
	if (temp != NULL) {
		while (temp->next != NULL) {
			temp->key->parent = NULL;

			struct DListNode* node = (struct DListNode*) malloc(sizeof(DListNode));
			node->root = temp->key;

			node->prev = Fib_Heap;
			node->next = Fib_Heap->next;

			Fib_Heap->next = node;
			node->next->prev = node;
			
			temp = temp->next;
		}

		Fib_Heap->next->prev = Fib_Heap->prev;
		Fib_Heap->prev->next = Fib_Heap->next;
		Fib_Heap = Fib_Heap->next;
		struct FibNode** roots = (struct FibNode**) malloc(sizeof(struct FibNode*) * MAXNUM);
		for (int i=0; i<MAXNUM; i++) {
			roots[i] = NULL;
		}
		struct DListNode* iter = (struct DListNode*) malloc(sizeof(struct DListNode*));
		iter = Fib_Heap->next;

		//printf("Building Array...\n");
		while (iter != Fib_Heap) {
			//printf("Futok...!");
			int r = iter->root->rang;
			if (roots[r] == NULL ) {
				roots[r] = iter->root;
			}
			else {
				struct FibNode* update = iter->root;
				while (roots[r] != NULL) {
					if (update->key < roots[r]->key) {
						struct FibListNode* newchild = (struct FibListNode*) malloc(sizeof(struct FibListNode));
						newchild->key = roots[r];
						if (update->childs == NULL) {
							newchild->next = NULL;
						}
						else {
							newchild->next = update->childs;
						}
						update->childs = newchild;
						update->rang++;
						roots[r]->parent = update;

						//update array
						
						
						if (roots[r+1] != NULL) {
							roots[r] = NULL;
							r++;
						}
						else {
							roots[r] = NULL;
							roots[r+1] = update;
						}
					}
					else {
						struct FibListNode* newchild = (struct FibListNode*) malloc(sizeof(struct FibListNode));
						newchild->key = update;
						if (roots[r]->childs == NULL) {

							newchild->next = NULL;
						}
						else {
							newchild->next = roots[r]->childs;
						}
						roots[r]->childs = newchild;
						roots[r]->rang++;
						update->parent = roots[r];

						update = roots[r];

						if (roots[r+1] != NULL) {
							roots[r] = NULL;
							r++;
						}
						else {
							roots[r+1] = roots[r];
							roots[r] = NULL;
						}
					}
					//printf("Merging Done!\n");
				}
			}
			iter = iter->next;
		}

		//printf("Array Ready!\n");
		iter = Fib_Heap->next;
		while (iter != Fib_Heap) {
			//printf("Root: %d %f\n", iter->root->nodeNum, iter->root->key);
			iter = iter->next;
		}

		iter = Fib_Heap->prev;
		while (iter != Fib_Heap) {
			//printf("Root2: %d %f\n", iter->root->nodeNum, iter->root->key);
			iter = iter->prev;
		}


		iter = Fib_Heap->next;
		while (iter != Fib_Heap) {
			if (iter->root->parent != NULL) {

				//printf("Useless Node found!\n");
				iter->prev->next = iter->next;
				iter->next->prev = iter->prev;
			}
			iter = iter->next;
		}
			
		iter = Fib_Heap->next;
		while (iter != Fib_Heap) {
			//printf("Root: %d %f\n", iter->root->nodeNum, iter->root->key);
			iter = iter->next;
		}

		//printf("Searching min...\n");

		double min = MAXXX;
		struct DListNode* minind = NULL;
		iter = Fib_Heap->next;
		while (iter != Fib_Heap) {

			if (iter->root->key < min){
				min = iter->root->key;
				minind = iter;
			}

			iter = iter->next;
		}
		if (minind != NULL) {
			Fib_Heap = minind; 
		}
	}
	else {
		if (Fib_Heap == Fib_Heap->next) {
			return 0;
		}
		//printf("Hahooo!!\n");
		Fib_Heap->next->prev = Fib_Heap->prev;
		Fib_Heap->prev->next = Fib_Heap->next;
		Fib_Heap = Fib_Heap->next;

		double min = MAXXX;
		struct DListNode* minind = NULL;
		struct DListNode* iter = Fib_Heap->next;
		
		
		min = iter->root->key;
		minind = iter;
	
		while (iter != Fib_Heap) {

			if (iter->root->key <= min){
				min = iter->root->key;
				minind = iter;
			}
			//printf("Iter: %d\n", iter->root->nodeNum);

			iter = iter->next;
		}
		Fib_Heap = minind; 
		//printf("Hova mind futsz??\n>");
		return 0;
	}
	return 0;
}

int deckey(struct FibNode* node, double value) {
	node->key = value;
	if (node->parent != NULL) {
		if (value < node->parent->key) {
			struct DListNode* boss = (struct DListNode*) malloc (sizeof(struct DListNode));
			boss->root = node;
			boss->prev = Fib_Heap;
			boss->next = Fib_Heap->next;
			Fib_Heap->next = boss;
			boss->next->prev = boss;

			if (value < Fib_Heap->root->key) {
				Fib_Heap = boss;
			}
			struct FibNode* temp = node->parent;
			node->parent = NULL;
			while ((temp->parent != NULL) && (temp->marked != 0)) {
				struct DListNode* boss = (struct DListNode*) malloc (sizeof(struct DListNode));
				boss->root = temp;
				boss->prev = Fib_Heap;
				boss->next = Fib_Heap->next;
				Fib_Heap->next = boss;
				boss->next->prev = boss;

				temp = temp->parent;
				boss->root->parent = NULL;
				if (boss->root->key < Fib_Heap->root->key) {
					Fib_Heap = boss;
				}
			}
			if (temp->marked == 0) {
				if (temp->parent != NULL) {
					temp->marked = 1;
				}
			}
		}
	}
	return 0;
}
int main(int argc, char* argv[]) {

	//printf("Inputs: %s \n %s \n", argv[0], argv[1]);

	FILE* in;
	in = fopen("dijkstra.in", "r");
	if (in == NULL) {
		printf("Can't open input!\n");
		getchar();
		return 0;
	}

	char* line;
	line = (char*) malloc(sizeof(char) * LINE_LENGTH);

	// read n and m
	int n, m;
	if ( fgets(line, LINE_LENGTH, in) != NULL ) {
		char* temp;
		temp = strtok(line, " \n");
		n = atoi(temp);
		temp = strtok(NULL, " \n");
		m = atoi(temp);
	}
	else {
		printf("Input Syntax Error! \n");
		getchar();
		return 0;
	}


	struct ListNode** neighbourhoodList = (struct ListNode**) malloc(n * sizeof(struct ListNode*));
	for (int i=0; i<n; i++) {
		neighbourhoodList[i] = NULL;
	}

	double** weights = (double**) malloc(sizeof(double*) * n);
	for (int i=0; i<n; i++) {
		weights[i] = (double*) malloc(sizeof(double) * n);
	}

	while ( fgets(line, LINE_LENGTH, in) != NULL ) {
		char* temp;
		temp = strtok(line, " \n");
		int from = atoi(temp);
		temp = strtok(NULL, " \n");
		int to = atoi(temp);
		temp = strtok(NULL, " \n");
		double value = atof(temp);
		weights[from-1][to-1] = value;

		//insert Node
		struct ListNode* t = (struct ListNode*) malloc(sizeof(struct ListNode));
		t->key = to-1;
		if (neighbourhoodList[from-1] == NULL) {
			t->next = NULL;
		}
		else {
			t->next = neighbourhoodList[from-1];
		}
		neighbourhoodList[from-1] = t;
	}

	fclose(in);

	for (int i=0; i<n; i++) {
		struct ListNode* t = neighbourhoodList[i];
		printf("%d: ", i+1);
		if (t != NULL) {
			printf(" %d ", t->key+1);
			while (t->next != NULL) {
				t = t->next;
				printf(" %d ", t->key+1);
			}
		}
		else { 
			printf("Empty!");
		}

		printf(" \n");
	}

	Fib_Heap = (struct DListNode*) malloc(sizeof(struct DListNode));
	Fib_Heap->root = NULL;
	Fib_Heap->next = NULL;
	Fib_Heap->prev = NULL;

	struct FibNode** adress = (struct FibNode**) malloc(n * sizeof(struct FibNode*));

	int start = 0;

	for (int i=0; i<n; i++) {
		if (i == start) {
			adress[i] = insertFib(0, i);
		}
		else {
			adress[i] = insertFib(MAXXX, i);
		}
	}

	printf("Mind: %f %d \n", getMin(), getMinIndex());

	int* prev = (int*) malloc(sizeof(int) * n);
	for (int i=0; i<n; i++) {
		prev[i] = -1;
	}

	double* dist = (double*) malloc(sizeof(double) * n);
	for (int i=0; i<n; i++) {
		dist[i] = 0;
	}

	int* Q = (int*) malloc(sizeof(int) * n);
	for (int i=0; i<n; i++) {
		Q[i] = 1;
	}
	int Q_size = n;
	while (Q_size != 0) {
		int u = getMinIndex();
		int min = getMin();
		dist[u] = min;
		printf("Min: %f %d \n", getMin(), getMinIndex());
		deleteMin();
		//printf("After Delete, Min: %f %d \n", getMin(), getMinIndex());

		if (min == MAXXX) {
			break;
		}

		Q[u] = 0;
		Q_size--;


		struct ListNode* t = neighbourhoodList[u];
		while (t != NULL) {
			if (Q[t->key] == 1) {
				double alt = min + weights[u][t->key];
				if (alt < adress[t->key]->key) {
					//printf("DecKey(%d; %f -> %f) running...\n", adress[t->key]->nodeNum, adress[t->key]->key, alt);
					deckey(adress[t->key], alt);
					//printf("Done!\n");
					prev[t->key] = u;
				}
			}
			t = t->next;
		}


	}

	/*int u = end;
	struct ListNode* path = NULL;
	while (prev[u] != -1) {
		if (path == NULL) {
			struct ListNode* first = (struct ListNode*) malloc(sizeof(struct ListNode));
			first->key = prev[u];
			first->next = NULL;
			path = first;
		}
		else {
			struct ListNode* first = (struct ListNode*) malloc(sizeof(struct ListNode));
			first->key = prev[u];
			first->next = path;
			path = first;
		}
		u = prev[u];
	}

	printf ("Min Dist: %f \n", getMin());
	struct ListNode* result = path;
	printf("Min Path: ");
	while (result != NULL) {
		printf("%d ", result->key);
		result = result->next;
	}
	printf("\n"); */
	
	FILE* out;
	out = fopen("dijkstra.out", "w");
	for (int i=1; i<n; i++) {
		int t = dist[i];
		if (Q[i] == 1) {
			fprintf(out, "0 ");
		}
		else {
			fprintf(out, "%d ", t);
		}
	}
	fprintf(out,"\n");
	fclose(out);

	//printf("Ready!\n");
	getchar();
	return 0;
}