#include <stdio.h>

#define Nmax 100100
#define inf 100000000

struct nod{
	int info,cost;
	nod *next;
};
nod	*g[Nmax];

int n,m,c[Nmax],h[Nmax],p[Nmax],cont;
void down(int),adauga(int,int,int),swap(int,int),up(int),pop();

void swap(int a,int b)
{
	int tmp=h[a];
	h[a]=h[b];
	h[b]=tmp;
}

void adauga(int x,int y,int c)
{
	nod *current=new nod;
	current->info=y;
	current->cost=c;
	current->next=g[x];
	g[x]=current;
}

void up(int k)
{
	int poz;
	if(k>1)
		{
			poz=k>>1;
			if( c[h[poz]]>c[h[k]])
			{
				p[h[k]]=poz;
				p[h[poz]]=k;
				swap(k,poz);
				up(poz);
			}
		}
}


void pop()
{
	h[1]=h[cont];
	p[h[1]]=1;
	--cont;
	down(1);
}

void down(int k)
{
	int poz=k;
	while(k<=cont)
	{
		poz = k;
		if( (poz<<1) <=cont )
			{
				poz= k<<1;
				if(poz+1 <=k)
					if(c[h[poz+1]]<c[h[poz]])
						++poz;
			}
		else
			return ;
		if(c[h[k]]>c[h[poz]])
		{
			p[h[k]]=poz;
			p[h[poz]]=k;
			swap(k,poz);
			k=poz;
		}
		else
			return ;
	}
}
int main()
{
	int i,x,y,co;

	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(i=1;i<=m;++i)
		{
			scanf("%d%d%d",&x,&y,&co);
			adauga(x,y,co);
		}
	for(i=1;i<=n;++i)
		{
			p[i]=-1;
			c[i]=inf;
		}
	c[1]=0;
	p[1]=1;
	h[++cont]=1;

	while(cont)
	{
		int min=h[1];
		pop();

		nod *current= g[min];
		while(current)
		{
			if(c[current->info]>c[min]+current->cost)
				{
					c[current->info]=c[min]+current->cost;

					if(p[current->info] != -1)
						up( p[current->info]);
					else
						{
							h[++cont]=current->info;
							p[h[cont]]= cont;
							up(cont);
						}
				}
			current=current->next;
		}
	}
	for(i=2;i<=n;++i)
		if(c[i]!=inf)
			printf("%d ",c[i]);
		else
			printf("0 ");
	return 0;
}