#include <stdio.h>
#include <stdlib.h>
#define N 50005
#define INF 2000000000
int n,m,d[N],*a[N],*b[N],H[N],nr,poz[N];
void swap(int &x,int &y){
	int z=x;x=y;y=z;}
int min(int x,int y){
	if(x>y) return y;
	return x;
}
void sift(int n,int k){
	int son;
	do{
		son=0;
		if(2*k<=n) {
			son=2*k;
			if(2*k+1<=n && d[H[2*k+1]]<d[H[2*k]])
				son=2*k+1;
			if(d[H[son]]>=d[H[k]]) son=0;
			else  {
				poz[H[k]]=son;
				poz[H[son]]=k;
				swap(H[k],H[son]);
				k=son;
			}
		}
	}while(son);
}
void percolate(int n,int k){
	while(k>1 && d[H[k]]<d[H[k/2]]){
		poz[H[k]]=k/2;
		poz[H[k/2]]=k;
		swap(H[k],H[k/2]);
		k=k/2;
	}
}
void cut(int &n){
	H[1]=H[n];
	poz[H[1]]=1;
	--n;
	sift(n,1);
}
void build_heap(){
	int i;
	for(i=2;i<=n;i++){
		poz[i]=-1;
	}
	poz[1]=1;
	H[++nr]=1;
}
void solve(){
	int i,x;
	build_heap();
	while(nr){
		x=H[1];
		cut(nr);
		for(i=1;i<=a[x][0];i++)
			if(d[a[x][i]]>d[x]+b[x][i]){
				d[a[x][i]]=d[x]+b[x][i];
				if(poz[a[x][i]]!=-1)
					percolate(nr,poz[a[x][i]]);
				else {
					H[++nr]=a[x][i];
					poz[H[nr]]=nr;
					percolate(nr,poz[a[x][i]]);
				}
			}
	}
	for(i=2;i<=n;i++)
		printf("%d ",d[i] ==INF ? 0: d[i]);
}
int main(){
	int i,x,y,z;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		a[i]=(int*)malloc(4*17);b[i]=(int*)malloc(4*17);
		a[i][0]=b[i][0]=0;
		d[i]=INF;
	}
	d[1]=0;
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		a[x][0]=++b[x][0];
		if(a[x][0]%16==0) {
			a[x]=(int*)realloc(a[x], (a[x][0]+16)*4);
			b[x]=(int*)realloc(b[x], (b[x][0]+16)*4);
		}
		a[x][a[x][0]]=y; b[x][b[x][0]]=z;
	}
	solve();
	return 0;
}