#include<fstream.h>
long i,j,min,poz,a,b,c,d[20000],s[20000],t[20000],m,n,v[20000][20000],sum;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main ()
{
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]=2000;
for (i=1;i<=n;i++) {d[i]=v[1][i]; if(d[i]!=0&&d[i]<2000) t[i]=1;}
s[1]=1;
for (i=2;i<=n;i++)
	{min=2000;
	 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++) g<<d[i]<<" ";
return 0;
}