// 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 {
	int b, cost;
} pair;

pair *Next[NMAX]; // vecinii fiecarui nod

int numNext[NMAX], // numarul de vecini ai fiecarui nod
    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) {
	Next[a] = (pair*)realloc(Next[a], (numNext[a] + 1) * sizeof(pair));
	Next[a][numNext[a]].b = b;
	Next[a][numNext[a] ++].cost = cost;
}

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;
	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 (i = 0; i < numNext[here]; ++ i) {
			next = Next[here][i].b;
			cost = Next[here][i].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");
	
	return 0;
}