#include<stdio.h>
#define INF 1<<30
#define father(x) x>>1
#define left_son(x) x<<1
#define right_son(x) (x<<1)+1
int n,m;
int d[50001],h[50001],poz[50001],k;
struct graf
{
	int nod,cost;
	graf *next;
};
graf *a[50001];
void swap(int &x,int &y)
{
	int aux;
	aux=x;
	x=y;
	y=aux;
}
void adauga(int plec,int nod1,int cost1)
{
	graf *g=new graf;
	g->nod=nod1;
	g->cost=cost1;
	g->next=a[plec];
	a[plec]=g;
}
void citeste()
{
	int i,x,y,z;
	scanf("%d%d",&n,&m);
	for(i=0; i<m; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		adauga(x,y,z);
	}
}
void upheap(int y)
{
	int key=h[y];
	while((y>1)&&(d[key]<d[h[father(y)]]))
	{
		h[y]=h[father(y)];
		poz[h[father(y)]]=y;
		y=father(y);
	}
	h[y]=key;
	poz[key]=y;
}
void downheap(int y)
{
	int son=0;
	do
	{
		son=0;
		if(left_son(y)<=k)
		{
			son=left_son(y);
			if(right_son(y)<=k)
			{
				if(d[h[right_son(y)]]<d[h[son]])
					son=right_son(y);
			}
			if(d[h[son]]>=d[h[y]])
				son=0;
		}
		if(son)
		{
			swap(h[y],h[son]);
			poz[h[son]]=y;
			poz[h[y]]=son;
			y=son;
		}
	}while(son);
}
void dijkstra_heap()
{
	int i,min;
	graf *g;
	for(i=2; i<=n; i++)
		d[i]=INF;
	poz[1]=1;
	h[++k]=1;
	while(k)
	{
		min=h[1];
		swap(h[1],h[k]);
		k--;
		downheap(1);
		g=a[min];
		while(g)
		{
			if(d[g->nod]>d[min]+g->cost)
			{
				d[g->nod]=d[min]+g->cost;
				if(poz[g->nod])
					upheap(poz[g->nod]);
				else
				{
					h[++k]=g->nod;
					poz[h[k]]=k;
					upheap(k);
				}
			}
			g=g->next;
		}
	}
}
void scrie()
{
	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("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citeste();
	dijkstra_heap();
	scrie();
	return 0;
}