#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 50010
#define M 250010
#define INF INT_MAX
struct muchie{
       int x,y,c;
};
struct muchie v[M];
int *a[N],*b[N],n,m,d[N];
int h[N],poz[N];
inline int father(int i){
       return i/2;
}
inline int left_son(int i){
       return 2*i;
}
inline int right_son(int i){
       return 2*i+1;
}
void swap(int i,int j){
	int aux;
	aux=h[i];
	h[i]=h[j];
	h[j]=aux;
	poz[h[i]]=i;
	poz[h[j]]=j;
}
void down_heap(int i,int n){
	int maxim=i;
	if (left_son(i)<=n && d[h[maxim]]>d[h[left_son(i)]])
        maxim=left_son(i);
	if (right_son(i)<=n && d[h[maxim]]>d[h[right_son(i)]])
        maxim=right_son(i);
	if (i!=maxim){
		swap(i,maxim);
		down_heap(maxim,n);
	}
}
void up_heap(int i){
	int maxim;
	if (i!=1){
		if (d[h[i]]<d[h[father(i)]]){
			swap(i,father(i));
			up_heap(father(i));
		}
	}
}
void dijkstra(){
	int nh=n,i,x,y;
	h[1]=1;
	poz[1]=1;
	d[1]=0;
	while(nh){
		x=h[1];
		for(i=1;i<=a[x][0];++i){
			y=a[x][i];
			if(d[y]>d[x]+b[x][i]){
				/*
				h[++nh]=y;
				poz[y]=nh;
				*/            
				d[y]=d[x]+b[x][i];
				up_heap(poz[y]);
			}
		}
		swap(1,nh);
		--nh;
		down_heap(1,nh);
	}
}
void scan(){
	int i;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=0;i<m;++i){
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
        ++d[v[i].x];
	}
	for(i=1;i<=n;++i){
        a[i]=(int*)malloc(d[i]+1);
        b[i]=(int*)malloc(d[i]+1);
        a[i][0]=0;
        b[i][0]=0;
	}
	for(i=0;i<m;++i){
        a[v[i].x][++a[v[i].x][0]]=v[i].y;
        b[v[i].x][++b[v[i].x][0]]=v[i].c;
	}
	for(i=1;i<=n;++i){
        d[i]=INF;
		h[i]=i;
		poz[i]=i;
	}
}
void print(){
	int i;
	for (i=2;i<=n;++i)
		printf("%d ",(d[i]==INF)?0:d[i]);
	printf("\n");
}
int main(){
    scan();
    dijkstra();
    print();
	exit(0);
}