#include<fstream.h>   
int i,j,min,poz,a,b,c,d[1005],s[1005],t[1005],m,n,v[1005][1005],sum;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
void citire()
{
f>>n>>m;
for (i=0;i<m;i++) {f>>a>>b>>c;v[a][b]=c;}
for (i=1;i<=n;i++)
	 for (j=1;j<=n;j++)
		  if (v[i][j]==0 && i!=j) v[i][j]=1001;
}
int main ()
{
citire();
for (i=1;i<=n;i++) {d[i]=v[1][i]; if(d[i] && d[i]<1001) t[i]=1;}
s[1]=1;
for (i=2;i<=n;i++)
	 {
	 min=1001;
	 for (j=2;j<=n;j++)
		if (s[j]==0 && d[j]<min) {min=d[j];poz=j;}
	 s[poz]=1;
	 for (j=2;j<=n;j++)
		{
		sum=0;
		if (s[j]==0)
			{
			sum=d[poz]+v[poz][j];
			if (sum<d[j]) {d[j]=sum;t[j]=poz;}
			}
		}
	 }
for (i=2;i<=n;i++)
	{if (d[i]==1001) g<<0<<" ";
	else g<<d[i]<<" ";}
return 0;
}