// http://infoarena.ro/problema/dijkstra

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

#define INF INT_MAX
#define NMAX 50010

typedef struct node {
	int b, cost;
	struct node *next;
} Node;

Node *Next[NMAX]; // vecinii fiecarui nod
int n, m; // numarul de noduri respectiv muchii

int Dist[NMAX],  // distanta de la 1 la fiecare nod
    Used[NMAX];
int Heap[NMAX], Pos[NMAX], hsz;

inline void addEdge(int a, int b, int cost) {
	Node *newNode = (Node*)calloc(1, sizeof(Node));
	newNode->b = b;
	newNode->cost = cost;
	newNode->next = Next[a];

	Next[a] = newNode;
}

inline int cmp(int hi, int hj) {
	return (Dist[hi] < Dist[hj]);
}

inline void swap(int *a, int *b) {
	int c = *a;
	*a = *b;
	*b = c;
}

void swim(int p) {
	while (p / 2 >= 1 && !cmp(Heap[p / 2], Heap[p])) {
		swap(&Heap[p / 2], &Heap[p]);
		swap(&Pos[Heap[p / 2]], &Pos[Heap[p]]);
		p /= 2;
	}
	Pos[Heap[p]] = p;
}

void sink(int p) {
	int j;
	while (2 * p <= hsz) {
		j = 2 * p;
		if (j  + 1 <= hsz && !cmp(Heap[j], Heap[j + 1]))
			++ j;
		if (!cmp(Heap[p], Heap[j])) {
			swap(&Heap[p], &Heap[j]);
			swap(&Pos[Heap[p]], &Pos[Heap[j]]);
			p = j;
		} else
			break;
	}
}

void heapInsert(int val) {
	assert(val != n);
	Heap[++ hsz] = val;
	Pos[val] = hsz;
	swim(hsz);
}

int heapPop() {
	int tmp = Heap[1];
	Pos[Heap[hsz]] = 1;	
	swap(&Heap[hsz --], &Heap[1]);
	sink(1);
	return tmp;
}

void heapChangePriority(int pos, int val) {
	char shouldSink = val > Dist[Heap[pos]];
	Dist[Heap[pos]] = val;
	if (shouldSink)
		sink(pos);
	else
		swim(pos);

}

void dijkstra(int here) {
	int i;
	for (i = 0; i < n; ++ i) {
		Dist[i] = INF;
		Used[i] = 0;
		heapInsert(i);
	}
	// Dist[here] = 0;
	heapChangePriority(Pos[here], 0);

	int next, cost;
	Node *curr;
	while (hsz > 0) {
		/*for (i = 1; i <= hsz; ++ i)
			fprintf(stderr, "(%d %d) ", Heap[i], Dist[Heap[i]]);
		fprintf(stderr, "\n\n");*/

		here = heapPop();
		Used[here] = 1;
		for (curr = Next[here]; curr != NULL; curr = curr->next) {
			next = curr->b;
			cost = curr->cost;
			if (Dist[here] == INF)
				continue;
			if (!Used[next] && Dist[next] > Dist[here] + cost) {
				// Dist[next] = Dist[here] + cost;
				heapChangePriority(Pos[next], Dist[here] + cost);
			}
		}
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d%d", &n, &m);

	int a, b, c, i;

	for (i = 0; i < m; ++ i) {
		scanf("%d%d%d", &a, &b, &c);
		addEdge(a - 1, b - 1, c);
	}

	dijkstra(0);
	for (i = 1; i < n; ++ i)
		if (Dist[i] == INF)
			printf("0 ");
		else
			printf("%d ", Dist[i]);
	printf("\n");
	
	Node *curr, *helper;
	for (i = 0; i < n; ++ i)
		for (curr = Next[i]; curr != NULL; curr = helper) {
			helper = curr->next;
			free(curr);
		}
	
	return 0;
}