#include <stdio.h>
#include <string.h>

#define NMAX 50010
#define INFI 2000000000
#define MOD (1<<10)


typedef struct nod
{
	long v, cost;
	nod *urm;
} *pnod;
pnod list[NMAX];
long n, m;
long cost[NMAX];


void baga(int x, int y, int cost)
{
	pnod aux = new nod;

	aux -> v = y;
	aux -> cost = cost;
	aux -> urm = list[x];
	list[x] = aux;
}


void read()
{
	long i, x, y, cost;
	scanf("%ld %ld", &n, &m);
	for(i = 1; i <= m; ++i)
	{
		scanf("%ld %ld %ld", &x, &y, &cost);
		baga(x, y, cost);
	}
}

void bf()
{
	int inc, sf, x;
	pnod it;
	int i;
	int c[MOD*2];
	int d, next;

	for(i = 1; i <= n; ++i)
		cost[i] = INFI;

	inc = sf = 1;
	c[1] = 1;
	cost[1] = 0;

	while(inc <= sf)
	{
		x = c[ inc%MOD ];
		inc++;
		for(it = list[x]; it != NULL; it = it -> urm)
		{
			next = it -> v;
			d    = it -> cost;

			if(cost[next] > cost[x]+d)
			{
				cost[next] = cost[x]+d;
				++sf;
				c[ sf%MOD ] = next;
			}
		}
	}
}


int main()
{
	int i;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	read();


	bf();


	for(i = 2; i <= n; ++i)
		if(cost[i] == INFI)
			printf("0 ");
		else
			printf("%d ", cost[i]);


	return 0;
}