#include<fstream.h>
#include<iostream.h>

long i,t,v[501000][3],n,m,d[51000],u,j,c,a,b,poz[51000],s,cur,viz[51000],mm,k;

int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	u=(1<<30);
	for(i=2;i<=n;i++)
		d[i]=u;
	for(i=1;i<=m;i++)
	{
		f>>a>>b>>c;
		v[++k][0]=b;
		v[k][1]=poz[a];
		v[k][2]=c;
		poz[a]=k;
	}
	s=0;
	cur=1;
	while(s<n)
	{
		viz[cur]=1;
		s++;
		t=poz[cur];
		while(t)
		{
			if(!viz[v[t][0]])
				if(d[v[t][0]]>d[cur]+v[t][2])
					d[v[t][0]]=d[cur]+v[t][2];
			t=v[t][1];
		}
		i=1;
		while(viz[i])i++;
		mm=i;
		for(j=i+1;j<=n;j++)
			if(d[mm]>d[j]&&!viz[j])
				mm=j;
		cur=mm;
	}
	for(i=2;i<=n;i++)
		if(d[i]==u)g<<"0 ";
		else
			g<<d[i]<<' ';
	return 0;
}