#include<stdio.h>   
typedef struct nod{
	long info;
	long dist;
	nod *next;
}*pnod;   
pnod prim[50002],pp;   
long int n,m,i,a,b,c,h[50002],ph[50002],d[50002],i8,lh,nv,viz[50002],dv,nn,dn,aux;
void add(pnod &p,long j,long c);
void read();   
void hd(long int ic);   
void hu(long int ic);   
void sh(long int i1,long int i2);   
int main()   
{   
    freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
    i8=1000000000;   
    for(i=1;i<=n;i++){
		h[i]=i;
		ph[i]=i;
		d[i]=i8;
	}
	d[1]=0;
	lh=n;   
    while(lh && d[h[1]]<i8){
		nv=h[1];
		viz[nv]=1;
		dv=d[nv];
		h[1]=h[lh];
		ph[h[1]]=1;
		lh--;
		hd(1);
		pp=prim[nv];
		while(pp){
			if(viz[pp->info])
				pp=pp->next;
			else{
				if(d[pp->info]>dv+pp->dist){
					d[pp->info]=dv+pp->dist;
					hu(ph[pp->info]);
				}
				pp=pp->next;
			}
		}
	}   
    for(i=2;i<=n;i++){
		if(d[i]==i8)
			d[i]=0;
		printf("%ld ",d[i]);
	}   
    printf("\n");
	fcloseall();
	return 0;   
}
void add(pnod &p,long j,long c)   
{   
    nod *q=new nod;   
    q->info=b;   
    q->dist=c;   
    /*if(!prim[a]){
		paux->next=0;
		prim[a]=paux;
		return;
	}
    q->next=prim[a];
	prim[a]=q;*/
	q->next=p;
	p=q;
}
void read()
{
	scanf("%ld %ld",&n,&m);
	for(i=1;i<=m;i++){
		scanf(,"%ld %ld %ld",&a,&b,&c);
		add(prim[a],b,c);
	}
}
void hd(long int ic)   
{   
    long int is,is1;   
    is=ic<<1;
	is1=is|1;   
    if(is>lh)
		return;   
    if(is<lh)
		if(d[h[is1]]<d[h[is]])
			is=is1;   
    if(d[h[is]]<d[h[ic]]){
		sh(is,ic);
		hd(is);
	}   
}   
void hu(long int ic)   
{   
    long int is;   
    is=ic>>1;   
    if(!is)
		return;   
    if(d[h[is]]>d[h[ic]]){
		sh(is,ic);
		hu(is);
	}   
}   
void sh(long int i1,long int i2)   
{   
    aux=h[i1];
	h[i1]=h[i2];
	h[i2]=aux;   
    ph[h[i1]]=i1;
	ph[h[i2]]=i2;   
}