#include<stdio.h>

#define MAXN 50001
#define inf 10000000

long n,m,e,q[MAXN],iq[MAXN],d[MAXN],l=1;
struct nod{ int v,c;
            nod * next;
		  } * v[MAXN];

void citire()
{   long i,x,y,c;
    nod *p;
	freopen("dijkstra.in","r",stdin);
    scanf("%ld%ld",&n,&m);
	for(i=1;i<=m;i++)
	{	scanf("%ld%ld%ld",&x,&y,&c);
		p=new nod;
		p->v=y;
		p->c=c;
		p->next=v[x];
		v[x]=p;
	}
	fclose(stdin);
}

void bford()
{	int i;
	nod *p;
	for(i=1;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	q[1]=1;
	iq[1]=1;
	e=1;
	while(l<=e)
	{	int nd=q[l];
	    l++;
	    iq[nd]=0;
		p=v[nd];
		while(p!=NULL)
		{	if(d[nd]+p->c<d[p->v])
			{	d[p->v]=d[nd]+p->c;
		        if(!iq[p->v])
				{	q[++e]=p->v;
					iq[p->v]=1;
				}
			}
			p=p->next;
		}
	}
}

int main()
{   freopen("dijkstra.out","w",stdout);
	citire();
	bford();
	for(int i=2;i<=n;i++)
		if(d[i]==inf) printf("0 ");
			else  printf("%ld ",d[i]);
	fclose(stdout);
	return 0;
}