#include<stdio.h>
#define N_MAX 1024*50
#define INFINIT 0x7FFFFFFF

struct entry
{
	int val, cost;
	entry * next;
} *start[N_MAX], *stop[N_MAX], *p;

struct heap
{
	int min, nod;
} h[N_MAX], tmp;

int n, m, best[N_MAX];
int poz[N_MAX];

void init_heap()
{
	int i;
	for (i=1; i<=n; i++)
	{
		h[i].min=INFINIT;
		h[i].nod=i;
		poz[i]=i;
	}
}

void urca(int unde)
{
	if ((unde/2>=1)&&(h[unde/2].min > h[unde].min))
	{
		poz[h[unde].nod]=unde/2;
		poz[h[unde/2].nod]=unde;
		tmp=h[unde/2];
		h[unde/2]=h[unde];
		h[unde]=tmp;
		urca(unde/2);
	}
	return;
}
void coboara(int unde)
{
	int fav=n+1;
	if (unde*2<=n)
		fav=unde*2;
	if ((unde*2+1<=n)&&(h[unde*2+1].min<h[unde*2].min))
		fav=unde*2+1;
	if ((fav<=n)&& (h[fav].min<h[unde].min) )
	{
		poz[h[unde].nod]=fav;
		poz[h[fav].nod]=unde;
		tmp=h[unde];
		h[unde]=h[fav];
		h[fav]=tmp;
		coboara(fav);
	}
}

void actualizare(int unde, int val)
{
	h[unde].min=val;
	if ((unde/2>=1)&&(h[unde/2].min > h[unde].min))
		urca(unde);
	else
		coboara(unde);
}

void add(int a, int b, int cost)
{
	p=new entry;
	p->next=NULL;
	p->val=b;
	p->cost=cost;
	if (start[a]==NULL)
	{
		start[a]=p;
		stop[a]=p;
	}
	else
	{
		stop[a]->next=p;
		stop[a]=stop[a]->next;
		
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	int i, a, b, cst, nr=0, st=1;
	scanf("%d %d", &n, &m);
	for (i=1; i<=m; i++)
	{
		scanf("%d %d %d", &a, &b, &cst);
		add(a, b, cst);
	}
	init_heap();
	for (i=1; i<=n; i++)
	{
		best[i]=INFINIT;
	}
	actualizare(poz[st], 0);
	
	while (nr<n)
	{

		if (h[1].min < best[ h[1].nod ] )
		{
			best[h[1].nod]=h[1].min;
			p=start[h[1].nod];
			while(p!=NULL)
			{
				if (( best[h[1].nod]+p->cost < h[poz[p->val]].min ) && (best[p->val]==INFINIT))
				{	
					actualizare(poz[p->val], best[h[1].nod]+p->cost);
				}
				p=p->next;
			}
		}
		actualizare(1, INFINIT);
		++nr;
	}
	for (i=2; i<=n; i++)
	{
		if (best[i]!=INFINIT)
			printf("%d ", best[i]);
		else printf("0 ");
	}
	fclose(stdout);
	return 0;
}