#import<fstream>
int a[250001][4],d[50001],n,k,o=1,i,j,c,m,p=1,I=2000000;
std::ifstream f{"dijkstra.in"};
std::ofstream g{"dijkstra.out"};
main()
{
	f>>n>>m;
	for(i=2;i<=n;i++)d[i]=I;
	for(i=1;i<=m;i++)
	    {	f>>a[i][1]>>a[i][2]>>a[i][3];
	        if(a[i][1]==1)d[a[i][2]]=a[i][3];
		}
	for(;o&&p<n;++p)
		for(o=0,k=1;k<=m;k++)
		{
			i=a[k][1];j=a[k][2];c=a[k][3];
			if(d[j]>d[i]+c)d[j]=d[i]+c,o=1;
		}
for(i=2;i<=n;i++)g<<(d[i]<I?d[i]:0)<<' ';
}