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

#define MAX 100000
#define INFINITY 999999
#define SIZE 5000

typedef struct pair {
	int v, cost;
} Pair;

typedef Pair V;

typedef struct list {
	V data;
	struct list *prev, *next;
}*List;
typedef struct graph {
	int V; // nr de noduri din graf
	int type; // 0 - neorientat ; 1 - orientat
	List *adjLists; // vectorul cu listele de adiacență
}*Graph;

typedef struct edge {
	int u, v, cost;
} Edge;
typedef struct arc {
	int u, cost;
} Arc;
typedef Arc* Type;

typedef struct heap {
	Type vector[MAX];
	int *map;
	int size;
	int capacity;
	int (*compare_func)(const void*, const void*);
} *Heap;

List initList(V data)
{
	List list;

	list = (List) calloc(1, sizeof(struct list));
	list->data = data;
	list->next = NULL;
	return list;
}

List addFirst(List list, V data)
{
	List new;

	if (list == NULL)
		return initList(data);
	new = initList(data);
	new->next = list;
	list->prev = new;
	return new;
}

List addLast(List list, V data)
{
	List new, tmp;

	if (list == NULL)
		return initList(data);
	new = initList(data);
	tmp = list;
	while (tmp->next != NULL)
		tmp = tmp->next;
	tmp->next = new;
	return list;
}

List deleteItem(List l, V data) {
	if(l == NULL) {
		return NULL;
	} else {
		List tmp = l, prev;
		if(tmp->data.v == data.v) {
			l = l->next;
			free(tmp);
			if(l)
				l->prev = NULL;
			return l;
		} else {
			prev = tmp;
			tmp = tmp->next;
		}
		while(tmp != NULL) {
			if(tmp->data.v == data.v) {
				prev->next = tmp->next;
				if (tmp->next != NULL)
					tmp->next->prev = prev;
				free(tmp);
				return l;
			}
			prev = tmp;
			tmp = tmp->next;
		}
		return l;
	}
}
void printList(List l){
	List tmp = l;
	printf("\n");
	while(tmp){
		printf("%d ", tmp->data.v);
		tmp = tmp->next;
	}
}

List freeList(List list)
{
	List tmp;

	if (list == NULL)
		return list;
	while (list != NULL) {
		tmp = list;
		list = list->next;
		free(tmp);
	}
	return NULL;
}


Graph initGraph(int V, int type)
{
	Graph g;
	int i;
	g = (Graph) calloc(1, sizeof(struct graph));
	g->V = V;
	g->adjLists = (List*) calloc(V + 1, sizeof(List));
	g->type = type;
	for (i = 0; i < V; i++) {
		g->adjLists[i] = NULL;
	}
	
	return g;
}

Graph insertEdge(Graph g, int u, int v, int cost)
{
	Pair p;
	p.v = v;
	p.cost = cost;
	// printf("%d %d %d\n", u, v, cost);
	g->adjLists[u] = addLast(g->adjLists[u], p);

	if (g->type == 0) {
		p.v = u;
		p.cost = cost;
		g->adjLists[v] = addLast(g->adjLists[v], p);
	}
	return g;
}

int isArc(Graph g, int u, int v)
{
	List tmp = g->adjLists[u];
	while (tmp != NULL) {
		if (tmp->data.v == v)
			return 1;
		tmp = tmp->next;
	}
	return 0;
}
Graph eliminate_edge(Graph g, int u, int v){
	Pair p;
	p.v = v;
	g->adjLists[u] = deleteItem(g->adjLists[u], p);
	return g;
}

int getCost(Graph g, int u, int v)
{
	List tmp = g->adjLists[u];
	while (tmp != NULL) {
		if (tmp->data.v == v)
			return tmp->data.cost;
		tmp = tmp->next;
	}
	return INFINITY;
}

void drawGraph(Graph g, char *name)
{
	int i, j;
	FILE *stream;
	char *buffer, *aux;
	List tmp;

	if (g == NULL || name == NULL)
		return;
	stream = fopen(name, "w");
	if (g->type == 0)
		fprintf(stream, "graph G {\n");
	else
		fprintf(stream, "digraph G {\n");
	fprintf(stream, "    node [fontname=\"Arial\", shape=circle, style=filled, fillcolor=yellow];\n");
	for (i = 0; i < g->V; i++) {
		tmp = g->adjLists[i];
		while (tmp != NULL) {
			if (g->type == 0) {
				if (i < tmp->data.v)
					fprintf(stream, "    %d -- %d;\n", i, tmp->data.v);
			}
			else
				fprintf(stream, "    %d -> %d;\n", i, tmp->data.v);
			tmp = tmp->next;
		}
	}
	fprintf(stream, "}\n");
	fclose(stream);
	buffer = (char*) malloc(SIZE*sizeof(char));
	aux = (char*) malloc(SIZE*sizeof(char));
	strncpy(aux, name, strlen(name) - 4);
	aux[strlen(name) - 4] = '\0';
	sprintf(buffer, "dot %s | neato -n -Tpng -o %s.png", name, aux);
	system(buffer);
	free(buffer);
	free(aux);
}

void printGraph(Graph g)
{
	int i;
	if (g == NULL)
		return;
	if (g->type == 0)
		printf("Graf neorientat cu %d noduri\n", g->V);
	else
		printf("Graf orientat cu %d noduri\n", g->V);
	for (i = 0; i < g->V; i++) {
		printf("%d: ", i);
		List adj = g->adjLists[i];
		while (adj) {
			printf("(%d, %d) -> ", adj->data.v, adj->data.cost);
			adj = adj->next;
		}
		printf("NULL\n");
	}
}

Graph freeGraph(Graph graph)
{
	int i;
	if (!graph)
		return graph;
	// if (graph->visited)
	// 	free(graph->visited);
	// if (graph->start)
	// 	free(graph->start);
	// if (graph->end)
	// 	free(graph->end);
	if (graph->adjLists) {
		for (i = 0; i < graph->V; i++)
			graph->adjLists[i] = freeList(graph->adjLists[i]);
		free(graph->adjLists);
	}
	free(graph);
	return NULL;
}

Heap initHeap(int (*compare_func) (const void*, const void*)) {
	Heap h = (Heap) malloc(sizeof(struct heap));
	h->size = -1;
	h->capacity = 10000;
	h->compare_func = compare_func;
	return h;
}
int LeftChild(int index) {
	return 2 * index + 1;
}

int RightChild(int index) {
	return 2 * index + 2;
}

int Parent(int index) {
	return (index - 1) / 2;
}
int compare_func2 (const void * a, const void * b) {
	Type *pa = (Type*) a;
	Type *pb = (Type*) b;
	// if(*pa && *pb)
		return -((*pa)->cost - (*pb)->cost);
	// else
	// 	return 0;
}
Heap siftDown(Heap h, int index) {
	int maxIndex = index;
	Type *v = h->vector, aux;

	int l = 2 * index + 1;
	int r = 2 * index + 2;

	if (l <= h->size){
		if (r <= h->size && (v[l]->cost - v[r]->cost) > 0)
			maxIndex = r;
		else
			maxIndex = l;
	}

	if (index != maxIndex && v[index]->cost > v[maxIndex]->cost) {
		h->map[h->vector[maxIndex]->u] = index;
		h->map[h->vector[index]->u] = maxIndex;
		aux = h->vector[maxIndex];
		h->vector[maxIndex] =  h->vector[index];
		h->vector[index] = aux;
		// h = swapAndSiftDown(h, index, maxIndex);
		h = siftDown(h, maxIndex);
	}

	//HINT: Se va folosi funcția swapAndSiftDown
	return h;
}

Heap siftUp(Heap h, int index) {
	int parent = (index - 1) / 2;
	Type aux;
	// printf("%d\n", parent);
	Type *v = h->vector;
	// printf("%d %d\n", parent, index);
	// return -(v[index]->cost - v[parent]->cost);
	while (index > 0 && (v[index]->cost - v[parent]->cost) < 0) {
		// printf("%d %d\n", h->vector[index]->u, h->vector[parent]->u);
		// h = swapAndSiftDown(h, parent, index);
		h->map[h->vector[parent]->u] = index;
		h->map[h->vector[index]->u] = parent;
		aux = h->vector[parent];
		h->vector[parent] =  h->vector[index];
		h->vector[index] = aux;
		index = parent;
		parent = (index - 1) / 2;
	}
	return h;
}

Heap swapAndSiftDown(Heap h, int parent, int child) {
	Type aux;
	h->map[h->vector[parent]->u] = child;
	h->map[h->vector[child]->u] = parent;
	aux = h->vector[parent];
	h->vector[parent] =  h->vector[child];
	h->vector[child] = aux;
	return h;
}

Heap insertHeap(Heap h, Type element) {
	if (h->size  == h->capacity)
		printf("Eroare! Nu mai exista memorie alocata.\n");
	else{
		h->size = h->size + 1;
		// h->vector[h->size] = (Type) calloc(1, sizeof(Edge));
		h->vector[h->size] = element;
		h = siftUp(h, h->size);
	}
	return h;
}
int is_empty_heap(Heap h) {
	return (h->size < 0);
}

Type extract_root(Heap h) {
	if(h && h->size >= 0){
		Type result = h->vector[0];
		h->vector[0] = h->vector[h->size];
		h->map[h->size] = 0;
		h->size = h->size - 1;
		h = siftDown(h, 0);
		return result;
	}
	Type result = (Type) calloc(1, sizeof(Arc));
	result->u = -1;
	return result;
}

Heap freeHeap(Heap h) {
	h->size = 0;
	h->capacity = 0;
	int i;
	for(i = 0; i < h->size; i++)
		free(h->vector[i]);
	free(h);
	return NULL;
}


int *Dijkstra2(Graph g, int start) {
	int V = g->V, min_u, destination, distance, i;
	int cost;
	Heap h;
	Type min, element;
	List tmp;
	int *dist = (int*) calloc(V, sizeof(int));
	int *visiting = (int*) calloc(V, sizeof(int));
	

	h = initHeap(compare_func2);
	h->map = (int*) calloc(V, sizeof(int));

	// pentru fiecare element din minHeap
	// init_unic_sourse2(g, h, dist);
	for (i = 0; i < g->V; i++){
	 	dist[i] = INFINITY;
 		element = (Type) calloc(1, sizeof(Arc));
 		element->u = i;
 		element->cost = dist[i];
 		h = insertHeap(h, element);
 		h->map[i] = i;
 	}
	dist[start] = 0;
	h->vector[h->map[start]]->cost = 0;
	h = siftUp(h, start);

	while (!is_empty_heap(h)) {
		min = extract_root(h);
		min_u = min->u;
		visiting[min_u] = 1;
		h->map[min_u] = -1;
		tmp = g->adjLists[min_u];
		while (tmp != NULL){
			destination = tmp->data.v;
			// cost = tmp->data.cost;
			if(visiting[destination] != 1){
				distance = dist[min_u] + tmp->data.cost;
				if(dist[destination] > distance) {
					dist[destination] = distance;
					
						h->vector[h->map[destination]]->cost = dist[destination]; 
						h = siftUp(h, h->map[destination]);
				}
				// print_heap(h);
				// print_array(h->map, V);
				// relaxing_edge2(min->u, tmp->data.v, tmp->data.cost, dist, h);
			}
			tmp = tmp->next;
		}
	}
	return dist;
}
int main(){
	FILE *fin, *fout;
	int N, M, X;
	int u, v, cost, cap, min, j, min_index;
	char buffer[40], ch;
	int i, *array_dist, number;
	int *vertex_array;
	Graph g;

	fin = fopen("dijkstra.in", "rt");
	fgets(buffer, 20, fin);
	i = sscanf(buffer, "%d %d", &N, &M);

	g = initGraph( N, 0);

	vertex_array = (int *) calloc(M, sizeof(int));
	array_dist = (int *) calloc(N, sizeof(int *));
	
	// citirea datelor de intrare caracter cu caracter
	for (i = 0; i < M; i++) {
		fgets(buffer, 20, fin);
		cap = sscanf(buffer, "%d %d %d", &u, &v, &cost);
		g = insertEdge(g, u - 1, v - 1, cost);
	}
	// for(i = 0 ; i < X; i++)
	// 	for(j = i + 1; j < X; j++)
	// 		if(vertex_array[i] > vertex_array[j]){
	// 			cap = vertex_array[i];
	// 			vertex_array[i] = vertex_array[j];
	// 			vertex_array[j] = cap;
	// 		}
 
	array_dist = Dijkstra2(g, 0);
	fout = fopen("dijkstra.in", "wt");
	for (i = 1; i < N; i++)
		if(array_dist[i] != INFINITY)
			fprintf(fout, "%d ", array_dist[i]);
		else
			fprintf(fout, "0 ");
		
	fprintf(fout, "\n");
	fclose(fout);
}