#include<fstream.h>
#include<iostream.h>
int a[1000][1000],
   s[1000],t[1000],d[1000];
long x,y,i,j,max,k,n,m,z,min,nr;
ifstream f("test8.in");
ofstream h("dijkstra.out");
void citire()
	 {f>>n>>m;
	 for(i=1;i<=m;i++)
	{f>>x>>y>>z;
	 a[x][y]=z;
	}
	for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)  if(i!=j && a[i][j]==0)  a[i][j]=32000;
	x=1;
	}
int main()
{
citire();
for(i=1;i<=n;i++)
	d[i]=a[x][i];
s[x]=1;
for(i=1;i<=n;i++)
	 if(d[i]<32000 )  t[i]=1;
t[x]=0;
for(i=1;i<=n-1;i++)
  { min =32000;
	for(j=1;j<=n;j++)
			if(min>d[j] && s[j]==0) {min=d[j];k=j;}
		s[k]=1;
	for(j=1;j<=n;j++)
		if(d[j]>d[k]+a[k][j] && s[j]==0) {d[j]=d[k]+a[k][j];
				 t[j]=k;}
  }
for(i=2;i<=n;i++)
    h<<d[i]<<" ";

return 0;
}