#include <cstdio>

#define dim 50001
#define infinit 1 << 30

struct nod {
	int x, c;
	nod *urm;
};
nod *p[dim];

int n, m, k = 1;

int d[dim], heap[dim], poz[dim];

void add(nod *&p, int y, int c) {
	nod *q = new nod;
	q -> x = y;
	q -> c = c;
	q -> urm = p;
	p = q;
}

void citire() {
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d", &n, &m);
	for ( int i = 0; i < m; i++ ) {
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		add(p[x], y, c);
	}
}

void intersch(int t, int c) {
	int aux = heap[t];
	heap[t] = heap[c];
	heap[c] = aux;
}

void in_sus(int c) {
	while ( c > 1 )  {
		int t = c >> 1;
		if ( d[heap[t]] <= d[heap[c]] )
			break;
		poz[heap[c]] = t;
		poz[heap[t]] = c;
		intersch(t, c);
		c = t;
	}
}

void in_jos(int t){
	while ( t <= k ) {
		int c = t;
		if ( (t << 1) > k )
			return;
		c = t << 1;
		if ( c + 1 <= k )
			if ( d[heap[c+1]] < d[heap[c]])
				c++;
		if (d[heap[t]]<= d[heap[c]])
			return;
		poz[heap[t]] = c;
		poz[heap[c]] = t;
		intersch(t, c);
		t = c;
	}
}

void init() {
	for ( int i = 2; i <= n; i++ ){
		d[i] = infinit;
		poz[i] = -1;
		heap[i] = i;
	}
	d[1] = 0;
	poz[1] = 1;
	heap[1] = 1;
}

void dijkstra() {
	init();
	while ( k ) {
		int min = heap[1];
		intersch(1, k);
		poz[heap[1]] = 1;
		k--;
		in_jos(1);
		for (nod *q = p[min]; q; q = q->urm) {
			if (d[q->x] > d[min] + q->c ) {
				d[q -> x] = d[min] + q->c;
				if ( poz[q->x] != -1 )
					in_sus(poz[q->x]);
				else {
					heap[++k] = q->x;
					poz[heap[k]] = k;
					in_sus(k);
				}
			}
		}
	}
}
void afisare() {
	freopen("dijkstra.out","w", stdout);
	for ( int i = 2; i <= n; i++ )
		printf("%d ", d[i] == infinit ? 0 : d[i]);
	printf("\n");
}

int main() {
	citire();
	dijkstra();
	afisare();
	return 0;
}