#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;
};

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

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

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[k][0].a;j++){
      y=g[k][j].a;
      if(d[y]>d[k]+g[k][j].c)d[y]=d[k]+g[k][j].c;
      if(!u[y]){
	q[++l]=y;
	u[y]=1;
      }
    }
    u[k]=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;
}