#include<stdio.h>
struct nod{
	long inf,c;
	nod *urm;
}*l[10000];
FILE *f;
long n,nh,m,x[10000],d[10000],poz[10000];
void cit(){
	FILE *f;
	nod *p;
	long a,b,c,i;
	f=fopen("dijkstra.in","r");
	fscanf(f,"%ld%ld",&n,&m);
	for(i=1;i<=n;i++)
		l[i]=0;
	for(i=1;i<=m;i++){
		fscanf(f,"%ld%ld%ld",&a,&b,&c);
		p=new nod;
		p->inf=b;
		p->c=c;
		p->urm=l[a];
		l[a]=p;
	}
	fclose(f);
}
void swap(long i,long j){
	long aux;
	poz[x[i]]=j;
	poz[x[j]]=i;
	aux=x[i];
	x[i]=x[j];
	x[j]=aux;
}
void HeapUp(long k){
	if(k<=1)
		return;
	if(d[x[k]]<d[x[k/2]]){
		swap(k,k/2);
		HeapUp(k/2);
	}
}
void HeapDw(long r,long k){
	long st,dr,i;
	if(2*r<=k){
		st=d[x[2*r]];
		if(2*r+1<=k)
			dr=d[x[2*r+1]];
		else
			dr=st-1;
		if(st<dr)
			i=2*r;
		else
			i=2*r+1;
		if(d[x[r]]>d[x[i]]){
			swap(i,r);
			HeapDw(i,k);
		}
	}
}
void BuildH(long k){
	long i;
	for(i=1;i<=k;i++)
		HeapUp(i);
}
long scoate_heap(){
	swap(1,nh);
	poz[x[nh]]=0;
	nh--;
	HeapDw(1,nh);
	return x[nh+1];
}
void dijkstra(long r){
	long i,k;
	nod *p;
	for(i=1;i<=n;i++){
		x[i]=poz[i]=i;
		d[i]=2000000000;
	}
	d[r]=0;
	BuildH(n);
	nh=n;
	while(nh>0){
		k=scoate_heap();
		p=l[k];
		while(p){
			if(d[p->inf]>d[k]+p->c){
				d[p->inf]=d[k]+p->c;
				HeapUp(poz[p->inf]);
			}
			p=p->urm;
		}
	}
}
void afis(){
	long i;
	f=fopen("dijkstra.out","w");
	for(i=2;i<=n;i++)
		if(d[i]==2000000000)
			fprintf(f,"%ld ",0);
		else
			fprintf(f,"%ld ",d[i]);
	fclose(f);
}
int  main(){
	cit();
	dijkstra(1);
	afis();
	return 0;
}