#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const long MAX=50100;
long n,m,d[MAX],heap[MAX],i,x,y,c,lh,pos[MAX];
struct point{
	long x,c;
	point *leg;
}*lista[MAX],*p;

void heapup(long x){
	while(d[heap[x]]<d[heap[(x-1)/2]] && x>0){
		swap(heap[x],heap[(x-1)/2]);
		swap(pos[heap[x]],pos[heap[(x-1)/2]]);
		x=(x-1)/2;
	}
}

void heapdown(long x){
	while(x<lh){
		long fs=0x3f;long fd=0x3f;
		if(2*x+1>=lh)
			break;
		else fs=d[heap[2*x+1]];
		if(2*x+2<lh)
			fd=d[heap[2*x+2]];
		if(d[heap[x]]<fs && d[heap[x]]<fd)
			break;
		if(fs<fd){
			swap(heap[x],heap[2*x+1]);
			swap(pos[heap[x]],pos[heap[2*x+1]]);
			x=2*x+1;
		}
		else{
			swap(heap[x],heap[2*x+2]);
			swap(pos[heap[x]],pos[heap[2*x+2]]);
			x=2*x+2;
		}
	}
}

void heapin(long x){
	heap[lh++]=x;
	pos[x]=lh-1;
	heapup(lh-1);
}

long heapout(){
	long r=heap[0];
	swap(heap[0],heap[lh-1]);
	swap(pos[heap[0]],pos[heap[lh-1]]);
	heap[--lh]=0;
	if(lh>0)
		heapdown(0);
	return r;
}

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=0;i<m;i++){
		scanf("%ld%ld%ld",&x,&y,&c);
		p=new point;
		p->x=y;p->c=c;p->leg=lista[x];
		lista[x]=p;
	}
	memset(d,0x3f,sizeof(d));
	d[1]=0;lh=0;
	heapin(1);
	while(lh>0){
		x=heapout();
		for(p=lista[x];p!=0;p=p->leg){
			if(d[p->x]>d[x]+p->c)
				if(d[p->x]==0x3f3f3f3f){
					d[p->x]=d[x]+p->c;
					heapin(p->x);
				}
				else{
					d[p->x]=d[x]+p->c;
					heapup(pos[p->x]);
				}
		}
	}
	for(i=2;i<=n;i++)
		printf("%ld ",d[i]<0x3f3f3f3f ? d[i] : 0);
//	printf("%ld\n",d[n]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}