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

#define INF 4294967295
#define MAX_LINE_SIZE 8192

struct node {
	int v;
	int cost;
	struct node *next;
};

struct min_heap {
	int key;
	int val;
};

void complete_adjacent_list(struct node **element, char *line, int order)
{
        char *p = strtok(line, " \t");

        while (p) {
                int n, cost;
                sscanf(p, "%d,%d", &n, &cost);

		if (order != n) {
			struct node *node = calloc(1, sizeof(struct node));
			node->v = n;
			node->cost = cost;

			if (*element == NULL)
				*element = node;
			else {
				node->next = *element;
				*element = node;
			}
		}

                p = strtok(NULL, " \t\r");
        }
}


void print_min_heap(struct min_heap *min_heap, int *index, int n)
{
	int i;
	for (i = 1; i <= n; i++)
		printf("(%d,%d) ", min_heap[i].key, min_heap[i].val);
	printf("\n");
	for (i = 1; i <= n; i++)
		printf("%d, ", index[i]);
	printf("\n");
}

void heap_swap(struct min_heap *min_heap, int *index, int i, int j)
{
	if (i == j)
		return;

	int u = min_heap[i].val;
	int v = min_heap[j].val;

	struct min_heap aux = min_heap[i];
	min_heap[i] = min_heap[j];
	min_heap[j] = aux;

	int tmp = index[u];
	index[u] = index[v];
	index[v] = tmp;
}

void bubble_up(struct min_heap *min_heap, int *index, int heap_size)
{
	if (heap_size == 1)
		return;

	unsigned int key = min_heap[heap_size].key;
	int vertex = min_heap[heap_size].val;

	int parent = heap_size / 2;
	unsigned int parent_key = min_heap[parent].key;

	while (key < parent_key) {
		heap_swap(min_heap, index, index[vertex], parent);
		if (index[vertex] == 1)
			return;
		parent = index[vertex] / 2;
		parent_key = min_heap[parent].key;
	}
}

void heap_insert(struct min_heap *min_heap, unsigned int key, int *index, int vertex, int *heap_size)
{
	(*heap_size)++;

	min_heap[*heap_size].key = key;
	min_heap[*heap_size].val = vertex;
	index[vertex] = *heap_size;
	bubble_up(min_heap, index, *heap_size);
}

void bubble_down(struct min_heap *min_heap, int *index, int heap_size, int i)
{
	if (heap_size <= 1)
		return;

	unsigned int key = min_heap[i].key;

	unsigned int child1_key = INF;
	unsigned int child2_key = INF;

	if (2 * i <= heap_size)
		child1_key = min_heap[2 * i].key;
	if (2 * i + 1 <= heap_size)
		child2_key = min_heap[2 * i + 1].key;

	if (key > child1_key || key > child2_key) {
		int min_child = (child1_key < child2_key) ? 2 * i : 2 * i + 1;

		heap_swap(min_heap, index, min_child, i);
		bubble_down(min_heap, index, heap_size, min_child);
	}
}

struct min_heap heap_extract_min(struct min_heap *min_heap, int *index, int *heap_size)
{
	struct min_heap min = min_heap[1];

	heap_swap(min_heap, index, 1, *heap_size);
	(*heap_size)--;

	bubble_down(min_heap, index, *heap_size, 1);

	return min;
}

void heap_replace(struct min_heap *min_heap, unsigned int key, int *index, int vertex)
{
	int i = index[vertex];

	if (key < min_heap[i].key) {
		min_heap[i].key = key;

		bubble_up(min_heap, index, i);
	}
}

void dijkstra(struct node **nodes, int n, int start)
{
	struct min_heap *min_heap = calloc(n + 1, sizeof(struct min_heap));
	int heap_size = 0;
	int *index = malloc((n + 1) * sizeof(int));
	unsigned int *dist = malloc((n + 1) * sizeof(unsigned int));

	int i;
	for (i = 1; i <= n; i++) {
		index[i] = -1;
		dist[i] = INF;
	}

	dist[start] = 0;
	struct node *vertex = nodes[start];
	while (vertex) {
		heap_insert(min_heap, dist[start] + vertex->cost, index, vertex->v, &heap_size);
		vertex = vertex->next;
	}

	//print_min_heap(min_heap, index, n);

	for (i = 1; i < n; i++) {
		struct min_heap min = heap_extract_min(min_heap, index, &heap_size);

		dist[min.val] = min.key;

		struct node *vertex = nodes[min.val];
		while (vertex) {
			if (dist[vertex->v] == INF) {
				if (index[vertex->v] == -1)
					heap_insert(min_heap, dist[min.val] + vertex->cost, index, vertex->v, &heap_size);
				else
					heap_replace(min_heap, dist[min.val] + vertex->cost, index, vertex->v);
			}
			vertex = vertex->next;
		}
	}

	FILE *f = fopen("dijkstra.out", "w");
	for (i = 2; i <= n; i++)
		if (dist[i] == INF)
		//	fprintf(f, "%d: INF\n", i);
			fprintf(f, "0 ");
		else
		//	fprintf(f, "%d: %u\n", i, dist[i]);
			fprintf(f, "%u ", dist[i]);
	fclose(f);
}

int main()
{

	FILE *f = fopen("dijkstra.in", "r");

	int n, m, start = 1;
	//fscanf(f, "%d %d %d", &n, &m, &start);
	fscanf(f, "%d %d", &n, &m);

	struct node **nodes = calloc(n + 1, sizeof(struct node *));

	int i;
	for (i = 0; i < m; i++) {
		int u, v, cost;
		fscanf(f, "%d %d %d", &u, &v, &cost);

		struct node *vertex = calloc(1, sizeof(struct node));
		vertex->v = v;
		vertex->cost = cost;

		if (!nodes[u])
			nodes[u] = vertex;
		else {
			vertex->next = nodes[u];
			nodes[u] = vertex;
		}
	}

	fclose(f);

/*
	FILE *f = fopen("dijkstraData.txt", "r");

	int n = 200, start = 1;

	struct node **nodes = calloc(n + 1, sizeof(struct node *));

	int i;
	for (i = 1; i <= n; i++) {
		char line[MAX_LINE_SIZE] = {0};
		fgets(line, MAX_LINE_SIZE, f);
		int len = strlen(line);
		line[len - 1] = '\0';
		complete_adjacent_list(&nodes[i], line, i);
	}

	fclose(f);

	for (i = 1; i <= n; i++) {
		printf("%d: ", i);
		struct node *vertex = nodes[i];
		while (vertex) {
			printf("%d,%d ", vertex->v, vertex->cost);
			vertex = vertex->next;
		}
		printf("\n");
	}
*/

	dijkstra(nodes, n, start);

	return 0;
}