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

#define INFINITE (1 << 30)

typedef struct Edge
{
	int node;
	int cost;
} Edge;

typedef struct EdgeListNode
{
	Edge edge;
	struct EdgeListNode *next;
} EdgeListNode;

EdgeListNode* CreateEdgeListNode(Edge e)
{
	EdgeListNode *new_node = (EdgeListNode*)malloc(sizeof(EdgeListNode));
	new_node->edge = e;
	new_node->next = NULL;
	return new_node;
}

typedef struct EdgeList
{
	EdgeListNode *left, *right;
} EdgeList;

void InitList(EdgeList *l)
{
	l->left = l->right = NULL;
}

void AddToList(EdgeList *l, Edge e)
{
	EdgeListNode *new_node = CreateEdgeListNode(e);
	if (l->left == NULL) {
		l->left = l->right = new_node;
	} else {
		l->right->next = new_node;
		l->right = new_node;
	}
}

typedef struct Node
{
	int cost;
	EdgeList edges;
} Node;

void InitNode(Node *node)
{
	node->cost = INFINITE;
	InitList(&node->edges);
}

Node* CreateGraph(int n)
{
	Node *graph = (Node*)malloc(sizeof(Node) * n);
	int i;
	for (i = 0; i < n; ++i) {
		InitNode(&graph[i]);
	}
	return graph;
}

typedef struct HeapElem
{
	int node, cost;
} HeapElem;

typedef struct Heap
{
	HeapElem *vec;
	int *pos;
	int size;
} Heap;

static inline int Father(int n) { return n / 2; }
static inline int LeftSon(int n) { return 2 * n; }
static inline int RightSon(int n) { return 2 * n + 1; }

void InitHeap(Heap *h, int n)
{
	h->vec = (HeapElem*)malloc(sizeof(HeapElem) * (n + 1));
	h->pos = (int*)malloc(sizeof(int) * n);

	int i;
	for (i = 0; i < n; ++i) {
		h->pos[i] = 0;
	}
	h->size = 0;
}

void Swap(HeapElem *a, HeapElem *b)
{
	HeapElem aux = *a;
	*a = *b;
	*b = aux;
}

void HeapSwap(Heap *h, int a, int b)
{
	int node_a = h->vec[a].node;
	int node_b = h->vec[b].node;

	Swap(&h->vec[a], &h->vec[b]);
	h->pos[node_a] = b;
	h->pos[node_b] = a;
}

void Percolate(Heap *h, int node)
{
	if (node != 1) {
		int fa = Father(node);
		if (h->vec[node].cost < h->vec[fa].cost) {
			HeapSwap(h, node, fa);
			Percolate(h, fa);
		}
	}
}

void Sift(Heap *h, int node)
{
	if (LeftSon(node) <= h->size) {
		int son = LeftSon(node);
		if (RightSon(node) <= h->size) {
			int r_son = RightSon(node);
			if (h->vec[r_son].cost < h->vec[son].cost) {
				son = r_son;
			}
		}

		if (h->vec[son].cost < h->vec[node].cost) {
			HeapSwap(h, node, son);
			Sift(h, son);
		}
	}
}

void AddToHeap(Heap *h, int node, int cost)
{
	if (h->pos[node] != 0) {
		int pos = h->pos[node];
		h->vec[pos].cost = cost;

		if (pos != 1 && cost < h->vec[Father(pos)].cost) {
			Percolate(h, pos);
		} else {
			Sift(h, pos);
		}
	} else {
		h->vec[++h->size] = (HeapElem){node, cost};
		h->pos[node] = h->size;
		Percolate(h, h->pos[node]);
	}
}

static inline int Empty(Heap *h)
{
	return h->size <= 0;
}

HeapElem Pop(Heap *h)
{
	if (Empty(h)) {
		return (HeapElem){-1, -1};
	}

	HeapElem elem = h->vec[1];
	--h->size;

	if (h->size > 0) {
		HeapSwap(h, 1, h->size + 1);
		Sift(h, 1);
	}
	h->pos[elem.node] = 0;

	return elem;
}

void Dijkstra(Node g[], int n, int start)
{
	int i, node, cost;
	for (i = 0; i < n; ++i) {
		g[i].cost = INFINITE;
	}
	g[start].cost = 0;

	Heap queue;
	InitHeap(&queue, n);

	AddToHeap(&queue, start, 0);
	while (!Empty(&queue)) {
		HeapElem aux = Pop(&queue);
		node = aux.node;
		cost = aux.cost;

		EdgeListNode *it = g[node].edges.left;
		while (it) {
			int next = it->edge.node;
			int new_cost = cost + it->edge.cost;
			if (new_cost < g[next].cost) {
				g[next].cost = new_cost;
				AddToHeap(&queue, next, new_cost);
			}
			it = it->next;
		}
	}
}

int main()
{
	FILE *fin = fopen("dijkstra.in", "r");
	FILE *fout = fopen("dijkstra.out", "w");

	int n, m, x, y, c, i;
	fscanf(fin, "%d%d", &n, &m);

	Node *graph = CreateGraph(n);
	while (m--) {
		fscanf(fin, "%d%d%d", &x, &y, &c);
		AddToList(&graph[x - 1].edges, (Edge){y - 1, c});
	}

	Dijkstra(graph, n, 0);
	for (i = 1; i < n; ++i) {
		fprintf(fout, "%d ", (graph[i].cost == INFINITE ? 0 : graph[i].cost));
	}
	fprintf(fout, "\n");

	return 0;
}