#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]=1999999999;
for (i=1;i<=n;i++) {d[i]=v[1][i]; if(d[i]!=0) t[i]=1;}
s[1]=1;
for (i=2;i<=n;i++)
	{min=1999999999;
	 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[i]+v[i][j];
												  if (sum<d[j]) {d[j]=sum;t[j]=i;}
												 }
							  }
	}
for (i=2;i<=n;i++) g<<d[i]<<" ";
return 0;
}