#include<stdio.h>
#include<string.h>
#define maxn 50001
#define oo 0x3f3f3f3f
#define mod (1<<16)-1
FILE *f=fopen("dijkstra.in","r"), *g=fopen("dijkstra.out","w");

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

int n,m,i,d[maxn],prim,ultim,x,y,cost,Q[(1<<16)+13];
bool viz[maxn];
			
void citire()
{
	lista *q;
	fscanf(f,"%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		fscanf(f,"%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;
	d[1]=0;
	while(prim<=ultim)
	{
		x=Q[prim];
		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;
					ultim&=mod;
					Q[ultim]=p->nod;
				}
			}
		}
	}
	
	for(i=2; i<=n;i++)
		if(d[i]==oo) fprintf(g,"0 ");
	else fprintf(g,"%d ",d[i]);
		fprintf(g,"\n");
	
	fclose(f);
	fclose(g);
	return 0;
}