#include <stdio.h>
#include <malloc.h>
typedef struct nod{
	long long i,c;
	struct nod  *urm;}NOD;
#define MAX 999999999
#define EEE 50000
NOD *v[EEE];
long long d[EEE],n,m;
int s[EEE];
void citire()
{
	FILE *f;
	long long i,x,y,c;
	NOD *p;
	f=fopen("dijkstra.in","r");
	fscanf(f,"%lld %lld",&n,&m);
	for(i=1;i<=n;i++)d[i]=MAX;
	for(i=0;i<m;i++)
	{
		p=(NOD*)malloc(sizeof(NOD));
		fscanf(f,"%lld %lld %lld",&x,&y,&c);
		p->i=y; p->c=c; p->urm=v[x]; v[x]=p;
	}
	fclose(f);
}
void dijkstra()
{
	NOD *p;
	long long i,j,min,minc;
	p=v[1];
	while (p)
	{
		d[p->i]=p->c;
		p=p->urm;
	}
	s[1]=1;
	for(i=1;i<n;i++)
	{
		minc=MAX;
		for(j=1;j<=n;j++)
			if ((s[j]==0)&&(d[j]<minc)){
				min=j;
				minc=d[j];
			}
	 s[min]=1;
	 p=v[min];
	 if (minc==MAX) { printf("nu-i bine "); break; }
	 while (p)
	 {
		 if (d[p->i]>minc+p->c) d[p->i]=minc+p->c;
		 p=p->urm;
	 }
	}
}
void afis()
{
	FILE *f;
	long i;
	f=fopen("dijkstra.out","w");
	for(i=2;i<=n;i++)
		if(d[i]==MAX) fprintf(f,"0 ");
		else fprintf(f,"%lld ",d[i]);
		fclose(f);
}
int main()
{
	citire();
	dijkstra();
	afis();
	return 0;
}