//Dijikstra
#include <stdio.h>
#define INPUT "dijikstra.in"
#define OUTPUT "dijikstra.out"
#define NMAX 50001
#define MMAX 250001
#define INF 0x3f3f3f3f
int N, M;

int heap[NMAX], d[NMAX], poz[NMAX];
int ult;

struct nod
{
	nod *leg;
	int vec, cost;
}*graf[NMAX];

void citire()
{	
	scanf("%d %d", &N, &M);
	int i, c, x, y;
	for(i = 1; i <= N; ++i) graf[i] = NULL;
	for(i = 1; i <= M; ++i)
	{
		scanf("%d %d %d",&x, &y, &c);
		nod *p = new nod;
		p->cost = c;
		p->vec = y;
		p->leg = graf[x];
		graf[x] = p;
	}
}

void swap(int i, int j)
{
	int aux = heap[i];
	heap[i] = heap[j];
	heap[j] = aux;
	
	poz[heap[i]] = i;
	poz[heap[j]] = j;
}

void downheap(int i)
{
	while(i < ult)
	{
		int fiu = 0;
		if(i<<1 <= ult) fiu = i<<1;
		if((i<<1)+1 <= ult && d[heap[(i<<1)+1]] <= d[heap[fiu]]) fiu = (i<<1)+1;
		if(fiu && d[heap[fiu]] < d[heap[i]])
			swap(i, fiu), i = fiu;
		else break;
	}
}
void upheap(int i)
{
	while(i > 1)
	{
		if(d[heap[i>>1]] > d[heap[i]]) 
			swap(i, i>>1), i >>= 1;
		else break;
	}
}
void dijikstra(int src)
{
	int i;
	for(i = 2; i <= N; ++i) 
		d[i] = INF, poz[i] = -1;
	heap[++ult] = 1; poz[1] = 1;
	
	while(ult)
	{
		int min = heap[1];
		swap(1, ult); --ult;
		downheap(1);
		
		nod *p;
		for(p = graf[min]; p; p = p->leg)
			if(d[p->vec] > d[min] + p->cost)
			{
				d[p->vec] = d[min] + p-> cost;
				if(poz[p->vec] == -1)
					heap[++ult] = p->vec, 
					poz[p->vec] = ult;
				upheap(poz[p->vec]);
			}
	}
}

void afis()
{
	int i;
	for(i = 2; i < N; ++i)
		printf("%d ", d[i]==INF?0:d[i]);
	printf("%d\n", d[N]==INF?0:d[N]);
}
int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	citire();
	dijikstra(1);
	afis();
	return 0;
}