#include<stdio.h>
long nod,i,n,m,d,k,j,a1[250001],a2[250001],a3[250001],dist[50001],s[75001],ss[75001];
FILE *f,*g;
int main()
{ f=fopen("dijkstra.in","r"); g=fopen("dijkstra.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  for(i=1;i<=m;i++) fscanf(f,"%ld%ld%ld",&a1[i],&a2[i],&a3[i]);
  for(i=1;i<=n;i++) dist[i]=-1;
     s[1]=1; d=1; dist[1]=0; k=0;
     while(d!=0)
      { for(i=1;i<=d;i++)
	 { for(j=1;j<=m;j++)
	    if(s[i]==a1[j])
	     { if(dist[a2[j]]==-1)
		{ dist[a2[j]]=dist[s[i]]+a3[j];
		  k++; ss[k]=a2[j];
		}
	       else if(dist[s[i]]+a3[j]<dist[a2[j]])
		{ dist[a2[j]]=dist[s[i]]+a3[j];
		  k++; ss[k]=a2[j];
		}
	     }
	    else if(s[i]==a2[j])
	     { if(dist[a1[j]]==-1)
		{ dist[a1[j]]=dist[s[i]]+a3[j];
		  k++; ss[k]=a1[j];
		}
	       else if(dist[s[i]]+a3[j]<dist[a1[j]])
		{ dist[a1[j]]=dist[s[i]]+a3[j];
		  k++; ss[k]=a1[j];
		}
	     }
	 }
	for(i=1;i<=k;i++) s[i]=ss[i]; d=k; k=0;
      }
  for(i=2;i<=n;i++) if(dist[i]!=-1) fprintf(g,"%ld ",dist[i]); else fprintf(g,"0 ");
  fclose(g);
  return 0;
}