#include <stdio.h>

struct nod{
	nod *urm;
	long cost,nd;

} *p[1000],*aux,*auxx;

long d[1000],n,m,i,x,y,c,s[1000],k,min,j,gasit,poz,pinf=2147483647;

int main()
{	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;i++) d[i]=pinf;
	for(i=1;i<=m;i++){
		scanf("%ld%ld%ld",&x,&y,&c);
		aux=new nod;
		aux->urm=p[x];
		aux->nd=y,aux->cost=c;
		p[x]=aux;
		if (x==1) d[y]=c;
	}

	s[1]=1;

	for(i=2;i<=n;i++){
		min=pinf;
		for(j=2;j<=n;j++)
			if (d[j]<min) {min=d[j];poz=j;}
		s[poz]=1;



		for(aux=p[poz];aux!=NULL;aux=aux->urm)
		 if(!s[aux->nd])
		 {	if (d[aux->nd]>d[poz]+aux->cost)
				d[aux->nd]=d[poz]+aux->cost;

		 }
	}

	for(i=2;i<=n;i++)
	 if  (d[i]==-1) printf("0 ");
	 else printf("%ld ",d[i]);


	return 0;
}