#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 50001
#define Inf 1<<30

typedef struct graf{
       long nod,cost;} graf;

graf *a[N];

long n,m,d[N],u[N];

void add(long,long,long);
void citire();
void dijkstra();
void afisare();

int main(){
    citire();
    dijkstra();
    afisare();
    return 0;
}

void add(long x,long y,long c){
     a[x][0].nod++;
long w=a[x][0].nod;
     a[x]=(graf*)realloc(a[x],(w+1)*sizeof(graf));
     a[x][w].nod=y;
     a[x][w].cost=c;
}

void citire(){
long i,x,y,c;
     freopen("dijkstra.in","r",stdin);
     scanf("%ld %ld",&n,&m);
     for (i=1;i<=n;i++){
	     a[i]=(graf*)malloc(sizeof(graf));
	     a[i][0].nod=0;
     }
     for (i=1;i<=m;i++){
	     scanf("%ld %ld %ld",&x,&y,&c);
	     add(x,y,c);}
     for (i=2;i<=n;i++) d[i]=Inf;
     for (i=1;i<=a[1][0].nod;i++)
	     d[a[1][i].nod]=a[1][i].cost;
     u[1]=1;
}

void dijkstra(){
long min,pmin,i,j;
    while (1){
	      min=Inf;
	      for (i=1;i<=n;i++)
	          if (!u[i] && d[i]<min)
                 min=d[i],pmin=i;
           if (min==Inf) break;
           u[pmin]=1;
	       for (i=1;i<=a[pmin][0].nod;i++)
	           if (d[a[pmin][i].nod]>a[pmin][i].cost+min)
	              d[a[pmin][i].nod]=a[pmin][i].cost+min;
    }
}

void afisare(){
long i;
    freopen("dijkstra.out","w",stdout);
     for (i=2;i<=n;i++){
         assert(d[i]);
	     if (d[i]==Inf) printf("0 ");
	     else printf("%ld ",d[i]);}
     printf("\n");
}