#include <stdio.h>

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

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

long d[100],n,m,i,x,y,c,s[100],k,min,j,gasit,poz;

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]=-1;
	for(i=1;i<=n;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++){
		k=1;
		while(s[++k] && k<n && d[k]>=0);
		poz=k;
		for(j=k;j<=n;j++) if (d[j]<d[poz] && !s[k] && d[j]>=0) poz=j;
		s[poz]=1;

		for(aux=p[poz];aux!=NULL;aux=aux->urm)
		 if(!s[aux->nd])
		 {	if (d[aux->nd]==-1) d[aux->nd]=d[poz]+aux->cost;
			else 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;
}