#include<fstream.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;
	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;
	}
	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)
			g<<d[i]<<' ';
		else
			g<<"0 ";
	return 0;
}
/*
#include<fstream.h>
int d[50100],ver[250100],leg[250100],cost[250100],start[50100],pus[50100],cc[50100],c[50100];
int main()
{
	int x,y,co,n,m,q=0,i,u=(1<<30),t;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>co;
		ver[++q]=y;
		leg[q]=start[x];
		start[x]=q;
		cost[q]=co;
	}
	for(i=2;i<=n;i++)
		d[i]=u;
	c[++c[0]]=1;
	while(c[0])
	{
		for(i=1;i<=c[0];i++)
			pus[c[i]]=0;
		for(i=1;i<=c[0];i++)
		{
			t=start[c[i]];
			while(t)
			{
				if(d[ver[t]]>d[c[i]]+cost[t])
				{
					d[ver[t]]=d[c[i]]+cost[t];
					if(!pus[ver[t]])
					{
						pus[ver[t]]=1;
						cc[++cc[0]]=ver[t];
					}
				}
				t=leg[t];
			}
		}
		for(i=0;i<=cc[0];i++)
			c[i]=cc[i];
		cc[0]=0;
	}
	for(i=2;i<=n;i++)
		if(d[i]!=u)
			g<<d[i]<<' ';
		else
			g<<"0 ";
	return 0;
}*/