#include<fstream.h>
#define INF 32000
int a[50001][4],d[50001],n,k,x=1,i,j,c,m,nr=1;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{
    f>>n>>m;
	for(i=2;i<=n;i++)
		d[i]=INF;
	d[1]=0;
	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];
	}
	while(x && nr<n)
	{
		x=0;
			for(k=1;k<=m;k++)
				if(d[a[k][2]]>d[a[k][1]]+a[k][3])
					{d[a[k][2]]=d[a[k][1]]+a[k][3];x=1;}
			nr++;
	}

for(i=2;i<=n;i++) if(d[i]<INF) g<<d[i]<<" ";
else g<<0<<" ";
return 0;
}