#include<stdio.h>
#include<string.h>
#define maxn 50001
#define oo 0x3f3f3f3f
#define mod (1<<16)-1
#define DIM 8192   


struct lista{ int nod,c; 
			lista *urm;} *G[maxn];

int n,m,i,d[maxn],prim,ultim,x,y,cost,Q[(1<<16)+13],nr;
bool viz[maxn];
			

char ax[DIM];   
int pz;   

inline void cit(int &x)   
{   
    x=0;   
    while(ax[pz]<'0' || ax[pz]>'9')   
        if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;   
       
    while(ax[pz]>='0' && ax[pz]<='9')   
    {   
        x=x*10+ax[pz]-'0';   
        if(++pz==DIM)fread(ax, 1, DIM,stdin),pz=0;   
    }   
}   
  


void citire()
{
	freopen("dijkstra.in","r",stdin);
	lista *q;
	cit(n); cit(m);
	for(int i=1;i<=m;i++)
	{
		
		cit(x);cit(y);cit(cost);
		
		q= new lista;
		q->nod=y;
		q->c=cost;
		q->urm=G[x];
		G[x]=q;
	}
}

int main()
{
	citire();
	memset(d,oo,sizeof(d));
	memset(viz,0,sizeof(viz));
	
	lista *p;
	prim=ultim=1;
	Q[prim]=1;
	viz[1]=1;
	nr=1;
	d[1]=0;
	while(nr)
	{
		x=Q[prim];
		nr--;
		prim++;
		prim&=mod;
		viz[x]=0;
		for(p=G[x]; p!=NULL; p=p->urm)
		{
			if(d[x]+p->c<d[p->nod])
			{
				d[p->nod]=d[x]+p->c;
				if(!viz[p->nod])
				{
					viz[p->nod]=1;
					++ultim;
					nr++;
					ultim&=mod;
					Q[ultim]=p->nod;
				}
			}
		}
	}
	
	freopen("dijkstra.out","w",stdout);
	for(i=2; i<=n;i++)
		if(d[i]==oo) printf("0 ");
	else printf("%d ",d[i]);
		printf("\n");
	
	
	return 0;
}