#include <stdio.h>
#include <stdlib.h>
#define nume "dijkstra"
#define oo 0x3f3f3f3f
const int maxn=50001;
 

FILE *in=fopen(nume".in","r"),*out=fopen(nume".out","w");

struct graf{
  int a,c;
};

int *g[maxn],*c[maxn];
int n,m,d[maxn],q[maxn],q2[maxn],s,dest,u[maxn];

void citire(){
  int i,a,b,cost;
  fscanf(in,"%d%d",&n,&m);
  for(i=1;i<=n;i++){
    g[i]=(int*)realloc(g[i],sizeof(int));
    c[i]=(int*)realloc(c[i],sizeof(int));
    g[i][0]=0;
    c[i][0]=0;
  }
  for(i=1;i<=m;i++){
    fscanf(in,"%d%d%d",&a,&b,&cost);
    g[a][0]++;
    g[a]=(int*)realloc(g[a],sizeof(int)*(g[a][0]+1));
    g[a][g[a][0]]=b;

    c[a]=(int*)realloc(c[a],sizeof(int)*(g[a][0]+1));
    c[a][g[a][0]]=cost;
    
  }
}

void bellman(){
  int i,l,k,j,y;
  s=1;dest=n;
  for(i=1;i<=n;i++)d[i]=oo;
  l=1;
  q[l]=s;
  u[s]=1;
  d[s]=0;
  for(i=1;i<=l;++i){
    // k=q[i];
    for(j=1;j<=g[q[i]][0];++j){
      //      y=g[q[i]][j];
      if(d[g[q[i]][j]]>d[q[i]]+c[q[i]][j]){
	d[g[q[i]][j]]=d[q[i]]+c[q[i]][j];
	if(!u[g[q[i]][j]]){
	  q[++l]=g[q[i]][j];
	  //printf("(%d)",l);
	  u[g[q[i]][j]]=1;
      }
      }
    }
    u[q[i]]=0;
  }
  
}




int main(){

   citire();
   bellman();
  for ( int i = 2; i <= n; ++i )  
    fprintf(out, "%d ", d[i] == oo ? 0 : d[i]);       fprintf(out, "\n");  
  
  fclose(in);
  fclose(out);
  return 0;
}