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

#define NMAX 50010
#define INFI 2000000000
#define MOD ((1<<15)-1)


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


#define DIM 35000
char buf[DIM+10];
int poz;

int scan()
{
	int x = 0;
	while(buf[poz] < '0' || buf[poz] > '9')
		if(++poz == DIM)
			poz = 0, fread(buf, 1, DIM, stdin);

	while(buf[poz] >= '0' && buf[poz] <= '9')
	{
		x = x*10 + (buf[poz]-'0');

		if(++poz == DIM)
			poz = 0, fread(buf, 1, DIM, stdin);
        }

	return x;
}

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;


	fread(buf, 1, DIM, stdin);

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

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

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

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


	while(inc <= sf)
	{
		x = c[ inc&MOD ];
		inc++;
		uz[x] = 0;

		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;

				if(!uz[next])
				{
					++sf;
					c[ sf&MOD ] = next;
					++uz[next];
				}
			}
		}
	}
}


int main()
{
	long 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("%ld ", cost[i]);


	return 0;
}