#include<fstream.h>
#define u (1<<30)
#include<iostream.h>
int h[50100],hh[50100],d[50100],ver[250100],leg[250100],start[50100],L,cost[250100];
int root()
{
	int safe=h[1],son,aux,ls,rs,nod=1;
	hh[h[L]]=1;
	h[1]=h[L--];
	do
	{
		son=0;
		ls=(nod<<1);
		rs=1+ls;
		if(ls<=L)
		{
			son=ls;
			if(rs<=L&&d[h[rs]]<d[h[ls]])
				son=rs;
			if(d[h[son]]>=d[h[nod]])
				son=0;
		}
		if(son)
		{
			hh[h[son]]=nod;
			hh[h[nod]]=son;
			aux=h[nod];
			h[nod]=h[son];
			h[son]=aux;
			nod=son;
		}
	}
	while(son);
	hh[safe]=0;
	return safe;
}
int main()
{
	int n,m,t,nod,k,safe,q=0,x,y,c;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	while(m--)
	{
		f>>x>>y>>c;
		ver[++q]=y;
		leg[q]=start[x];
		start[x]=q;
		cost[q]=c;
	}
	for(t=1;t<=n;t++)
	{
		d[t]=u;
		hh[t]=h[t]=t;
	}
	d[1]=0;
	L=n;
	while(L)
	{
		nod=root();
		if(d[nod]!=u)
		{
			t=start[nod];
			while(t)
			{
				if(hh[ver[t]]&&d[ver[t]]>d[nod]+cost[t])
				{
					d[ver[t]]=d[nod]+cost[t];
					k=hh[ver[t]];
					safe=h[k];
					while(k>1&&d[h[k>>1]]>d[safe])
					{
						hh[h[k>>1]]=k;
						h[k]=h[k>>1];
						k>>=1;
					}
					hh[safe]=k;
					h[k]=safe;
				}
				t=leg[t];
			}
		}
		else
			L=0;
	}
	for(t=2;t<=n;t++)
		if(d[t]==u)
			g<<"0 ";
		else
			g<<d[t]<<' ';
	return 0;
}