#include<stdio.h>
#define N_ 50005
#define M_ 250005
#define OO 1<<30
int x,y,z,d[N_],h[M_],N,M;
int poz[M_],k;
void swap(int &x,int &y)
{
	int aux=x;
	x=y;
	y=aux;
}
struct graf
{
	int nod,cost;
	graf *next;
};
graf *a[N_];
void add(int n1,int n2, int cost1)
{
	graf *g=new graf;
	g->cost=cost1;
	g->nod=n2;
	g->next=a[n1];
	a[n1]=g;
}
void citire()
{
	scanf("%d%d",&N,&M);
	/*for (int i=1; i<=M; ++i)
	{
		scanf("%d%d%d",&x[i],&poz[i],&h[i]);
		++d[x[i]];
	}
	for (int i=1; i<=N; ++i)
	{
		a[i]=new int [1+d[i]];
		c[i]=new int [1+d[i]];
		a[i][0]=c[i][0]=0;
	}
	for (int i=1; i<=N; ++i)
	{
		a[x[i]][++a[x[i]][0]]=poz[i];
		c[x[i]][++c[x[i]][0]]=h[i];
	}*/
	for (int i=1; i<=M; ++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
}
void cobor(int y)
{
	int fiu=y;
	while (true)
	{
		if ((y<<1)<=k && d[h[y<<1]]<d[h[y]])
		    fiu=y<<1;
		if ((y<<1)+1<=k && d[h[(y<<1)+1]]<d[h[fiu]])
			fiu=(y<<1)+1;
		if (y==fiu)
			return;
		poz[h[fiu]]=y;
		poz[h[y]]=fiu;
		swap(h[fiu],h[y]);
		y=fiu;
	}
}
void urc(int y)
{
	int key=h[y];
	while (y-1 && d[key]<d[h[y>>1]])
	{
		poz[h[y>>1]]=y;
		h[y]=h[y>>1];
		y>>=1;
	}
	poz[key]=y;
	h[y]=key;
}
void dijkstra()
{
	for (int i=1; i<=N; ++i)
		d[i]=OO,h[i]=0,poz[i]=0;
	h[++k]=1;
	d[1]=0;
	poz[1]=k;
	graf *g;
	while (k)
	{
		int x=h[1];
		h[1]=h[k];
		poz[h[k]]=0;
		poz[h[1]]=1;
		--k;
		cobor(1);
		g=a[x];
		while (g)
		{
			if (d[g->nod]>d[x]+g->cost)
			{
				d[g->nod]=d[x]+g->cost;
				if (poz[g->nod])
					urc(poz[g->nod]);
				else
				{
					h[++k]=g->nod;
					poz[g->nod]=k;
					urc(k);
				}
			}
			g=g->next;
		}
	}
}
void afis()
{
	for (int i=2; i<=N; ++i)
		printf("%d ",(d[i]==OO)?0:d[i]);
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra();
	afis();
	return 0;
}