#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],grad[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);
    grad[a]++;
    g[a]=(int*)realloc(g[a],sizeof(int)*(grad[a]));
    g[a][grad[a]-1]=b;

    c[a]=(int*)realloc(c[a],sizeof(int)*(grad[a]));
    c[a][grad[a]-1]=cost;    
  }
}

void bellman(){
  int i,l,k,j,y;
  s=1;dest=n;
  for(i=1;i<=n;i++)d[i]=oo;
  l=0;
  q[l]=s;
  u[s]=1;
  d[s]=0;
  for(i=0;i<=l;++i){
    // k=q[i];
    for(j=grad[q[i]]-1;j;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;
}