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

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];
			



void citire()
{
	freopen("dijkstra.in","r",stdin);
	lista *q;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		
		scanf("%d %d %d",&x,&y,&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;
}