#include<stdio.h>
#include<time.h>
#include<iostream.h>
long x[600000],d[600000],t[600000],n,m,nh,r,poz[600000];
struct nod{
	long inf,c;
	nod *urm;
}*L[600000];
void cit(){
	freopen("dijkstra.in","r",stdin);
	scanf("%ld%ld",&n,&m);
	r=1;
	int k,i,j,c;
	nod *q;
	for(i=1;i<=n;i++)
		L[i]=0;
	for(k=1;k<=m;k++){
		scanf("%ld%ld%ld",&i,&j,&c);
		q=new nod;
		q->inf=j;
		q->c=c;
		q->urm=L[i];
		L[i]=q;
	}
	fclose(stdin);
	for(i=1;i<=n;i++){
		d[i]=320000;
		poz[i]=i;
		x[i]=i;
	}
}
void swap(int i,int j){
	int aux;
	poz[x[i]]=j;
	poz[x[j]]=i;
	aux=x[i];
	x[i]=x[j];
	x[j]=aux;
}
void heapdw(int r,int k){
	int 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);
		}
		else
			return;
	}
}
void heapup(int k){
	int i;
	if(k<=1)
		return;
	i=k/2;
	if(d[x[k]]<d[x[i]]){
		swap(k,i);
		heapup(i);
	}
	else
		return;
}
void buildh(int k){
	int i;
	for(i=1;i<=k;i++)
		heapup(i);
}
int scoate_heap(){
	swap(1,nh);
	poz[x[nh]]=0;
	nh--;
	heapdw(1,nh);
	return x[nh+1];
}
void dijkstra(){
	int k;
	nod *p;
	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;
				t[p->inf]=k;
				heapup(poz[p->inf]);
			}
			p=p->urm;
		}
	}
}
int main(){
	clock_t start, stop;
	float durata;
	start=clock();
	cit();
	dijkstra();
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;i++)
		if(d[i]==320000)
			printf("%d ",0);
		else
			printf("%ld ",d[i]);
	stop=clock();
	durata=(1.0 * stop-start)/CLOCKS_PER_SEC;
	//printf("\n%f\n", durata);
	fclose(stdout);
	return 0;
}