#include<stdio.h>
int d[50100],h[50100],hh[50100],ver[250100],leg[250100],cost[250100],start[50100],L;
void sift(int k)
{
	int son,aux,ls,rs;
	do
	{
		son=0;
		ls=(k<<1);
		rs=1+ls;
		if(ls<=L)
		{
			son=ls;
			if(rs<=L&&d[h[rs]]<d[h[son]])
				son=rs;
			if(d[h[son]]>=d[h[k]])
				son=0;
		}			
		if(son)
		{
			hh[h[son]]=k;
			hh[h[k]]=son;
			aux=h[son];
			h[son]=h[k];
			h[k]=aux;
			k=son;
		}
	}
	while(son);
}
void percolate(int k)
{
	int key=h[k];
	while(k>1&&d[h[k>>1]]>d[key])
	{
		hh[h[k>>1]]=k;
		h[k]=h[k>>1];
		k>>=1;
	}
	hh[key]=k;
	h[k]=key;
}
int root()
{
	int key=h[1];
	h[1]=h[L--];
	sift(1);
	hh[key]=0;
	return key;
}
int main()
{
	int x,y,c,m,nod,t,n,q=0,i;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	while(m--)
	{
		scanf("%d %d %d",&x,&y,&c);
		ver[++q]=y;
		leg[q]=start[x];
		start[x]=q;
		cost[q]=c;
	}
	int u=(1<<30);
	for(i=1;i<=n;i++)
	{
		h[i]=hh[i]=i;
		d[i]=u;
	}
	d[1]=0;
	L=n;
	while(L)
	{
		nod=root();
		t=start[nod];
		while(t)
		{
			if(hh[ver[t]])
				if(d[nod]+cost[t]<d[ver[t]])
				{
					d[ver[t]]=d[nod]+cost[t];
					percolate(hh[ver[t]]);
				}
			t=leg[t];
		}
	}
	for(i=2;i<=n;i++)
		if(d[i]!=u)
			printf("%d ",d[i]);
		else
			printf("%d ",0);
	return 0;
}