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

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

#define INF INT_MAX

typedef struct {
	int b, cost;
} pair;

pair **Next; // vecinii fiecarui nod

int *numNext, // numarul de vecini ai fiecarui nod
    n, m; // numarul de noduri respectiv muchii

int *Dist; // distanta de la 1 la fiecare nod

// #define NMAX 50000
int *Heap, *Pos, 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) {
	Heap = (int*)calloc(n + 1, sizeof(int));
	Pos = (int*)calloc(n, sizeof(int));
	int *Used = (int*)calloc(n, sizeof(int));

	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);
			}
		}
	}

	free(Used);
	free(Heap);
	free(Pos);
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	Next = (pair**)calloc(n, sizeof(pair*));
	numNext = (int*)calloc(n, sizeof(int));

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

	Dist = (int*)calloc(n, sizeof(int));
	dijkstra(0);
	for (i = 1; i < n; ++ i)
		if (Dist[i] == INF)
			printf("0 ");
		else
			printf("%d ", Dist[i]);
	printf("\n");
	
	free(Dist);
	for (i = 0; i < n; ++ i)
		free(Next[i]);
	free(Next);
	free(numNext);

	return 0;
}