/*
d= distanta (costu)
t= printele
s= vizitat sau nu
*/
#include<stdio.h>
int ii,a[1000][1000],t[100000],m,min=200000,n,d[100000],co,poz,s[100000],start,i,j;
FILE *in,*out;
void drum(int i)
{
 if(t[i])
  drum(t[i]);
 printf("%d ",i);
}
int main()
{
 in=fopen("dijkstra.in","rt");
 out=fopen("dijkstra.out","wt");
 fscanf(in,"%d  %d",&n, &m);
 
 

 
 start=1;
 s[start]=1;
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
    a[i][j]=min;
 
for(ii=1;ii<=m;ii++)
 {
  fscanf(in,"%d %d %d ",&i,&j,&co);
  a[i][j]=co;
 }


 for(i=1;i<=n;i++)
 {
  d[i]=a[start][i];
  if(i!=start)
   if(d[i]<min)
    t[i]=start;
 }

 
 for(i=1;i<n;i++)
 {
  min=20000;
  for(j=1;j<=n;j++)
   if(s[j]==0)
    if(d[j]<min)
    {
     min=d[j];
     poz=j;
    }
 s[poz]=1;
 for(j=1;j<=n;j++)
  if(s[j]==0)
   if(d[j]>d[poz]+a[poz][j])
   {
    d[j]=d[poz]+a[poz][j];
    t[j]=poz;
   }
 }

for(i=2;i<=n;i++)
	fprintf(out,"%d ",d[i]);
return 0;
}