#include <stdio.h>
typedef struct nod
{
	int x,c;
	nod *a;
} *pnod;
pnod 	a[50001];
int d[50001],heap[50001],poz[50001];
void add(int x,int y,int z)
{
	pnod p=new nod;
	p->x=y;
	p->c=z;
	p->a=a[x];
	a[x]=p;
}
void jos(int x,int nr)
{
	int min,aux;
	min=x;
	if (2*x<=nr&&d[heap[2*x]]<d[heap[min]])
		min=2*x;
	if (2*x+1<=nr&&d[heap[2*x+1]]<d[heap[min]])
		min=2*x+1;
	if (min!=x)
	{
		aux=heap[min];
		heap[min]=heap[x];
		heap[x]=aux;
		jos(min,nr);
	}
}
void sus(int x)
{
	int aux;
	if (x/2&&d[heap[x]]<d[heap[x/2]])
	{
		aux=heap[x];
		heap[x]=heap[x/2];
		heap[x/2]=aux;
		sus(x/2);
	}
}
void dijkstra(int x)
{
	int nr=1,y;
	pnod p;
	heap[1]=x;
	d[x]=0;
	while (nr)
	{
		y=heap[1];
		heap[1]=heap[nr];
		poz[y]=-1;
		nr--;
		jos(1,nr);
		for (p=a[y];p;p=p->a)
		{
			if (d[p->x]>d[y]+p->c||d[p->x]==-1)
			{
				d[p->x]=d[y]+p->c;
				if (poz[p->x]!=-1)
					sus(poz[p->x]);
				else
				{
					nr++;
					heap[nr]=p->x;
					sus(nr);
				}
			}
		}
	}
}
int main()
{
	FILE *in,*out;
	int i,A,B,C,n,m;
	in=fopen("dijkstra.in","r");
	out=fopen("dijkstra.out","w");
	fscanf(in,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(in,"%d%d%d",&A,&B,&C);
		add(A,B,C);
	}
	for (i=1;i<=n;i++)
	{
		d[i]=-1;
		poz[i]=-1;
	}
	dijkstra(1);
	for (i=2;i<=n;i++)
		fprintf(out,"%d ",d[i]==-1?0:d[i]);
	fprintf(out,"\n");
	fclose(in);
	fclose(out);
	return 0;
}