#include<stdio.h>
#include<stdlib.h>
#define N 50001
#define Inf 2000000000

struct graf{
       long nod,cost;} *a[N];

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

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

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]=(struct graf*)realloc(a[x],(w+1)*sizeof(struct 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]=(struct graf*)malloc(sizeof(struct 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;
    for (j=1;j<n;j++){
	min=Inf;
	for (i=1;i<=n;i++)
	    if (!u[i] && d[i]<min)
	       min=d[i],pmin=i;
	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++)
	 if (d[i]==Inf) printf("0 ");
	 else printf("%ld ",d[i]);
     printf("\n");
}