#include <stdio.h>
#include <math.h>

typedef struct nod {
	long x, c;
	nod *a;
} *pNod;
pNod v[50001];

#define inf  1 << 30 

long n, m, h[50001], poz[50001], d[50001], k, i, x, y, c;

void swap(long x, long y) {
	long aux = h[x];
	h[x] = h[y];
	h[y] = aux;
}

void urc(long p) {
	if (d[h[p]] < d[h[p / 2]] && p > 1)	{
		poz[h[p]] = p / 2;
		poz[h[p / 2]] = p;
		swap(p, p / 2);
		urc(p / 2);
	}
}

void cobor(long p) {
	long s, dr, max = p;
	s = p * 2;
	dr = p * 2 + 1;
	if (s <= k) {
		if (d[h[s]] < d[h[p]]) {
			max = s;
		}
	}
	if (dr <= k) {
		if (d[h[dr]] < d[h[max]]) {
			max = dr;
		}
	}
	if (max != p) {
		poz[h[p]] = max;
		poz[h[max]] = p;
		swap(p, max);
		cobor(max);
	}
}


void dijkstra() {
	long i, min;
	pNod p;
	for (i = 2; i <= n; ++i) {
		poz[i] = -1; 
		d[i] = inf;
	}
	poz[1] = h[++k] = 1;
	while (k) {
		min = h[1];
		swap(1, k);
		poz[h[1]] = 1;
		--k;
		cobor(1);
		for (p = v[min]; p != NULL; p = p -> a) {
			if (d[p -> x] > d[min] + p -> c) {
				d[p -> x] = d[min] + p -> c;
				if (poz[p -> x] != -1) {
					urc(poz[p -> x]);
				} else {
					h[++k] = p -> x;
					poz[h[k]] = k;
					urc(k);
				}
			}
		}
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	pNod p;
	scanf("%ld %ld", &n, &m);
	for (i = 1; i <= m; ++i) {
		scanf("%ld %ld %ld", &x, &y, &c);
		p = new nod;
		p -> x = y;
		p -> c = c;
		p -> a = v[x];
		v[x] = p;
	}	
	dijkstra();
	for (i = 2; i <= n; ++i) {
		if (d[i] == inf) {
			printf("0 ");
		} else {
			printf("%ld ", d[i]);
		}
	}
	printf("\n");
	return 0;
}