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

#define INF 4294967295

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

struct min_heap {
	int key;
	int val;
};

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, heap_size, parent);
		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, "0 ");
		else
			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);
/*
	for (i = 1; i <= n; i++) {
		printf("%d: ", i);
		struct node *vertex = nodes[i];
		while (vertex) {
			printf("%d, ", vertex->v);
			vertex = vertex->next;
		}
		printf("\n");
	}
*/

	dijkstra(nodes, n, start);

	return 0;
}