#include <stdio.h>
FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");
int n,m,h[50001],poz[50001],d[50001],i,x,y,c,k;
struct nod{int y; int d; nod* next;};
nod *a[50001];
const int inf=1<<30;
int add(int x, int y,int c)
{
	nod *q=new nod;
	q->y=y;
	q->d=c;
	q->next=a[x];
	a[x]=q;
	return 0;
}
int swap(int a,int b)
{
	int k=h[a];
	h[a]=h[b];
	h[b]=k;
	return 0;
}
int sift(int x)
{
	int max;
	while (x<=k)
	{
		max=x;
		if (x*2<=k)
		{
			max=x*2;
			if (max+1<=k)
				if (d[h[max]]>d[h[max+1]])
					max++;
		}
		else return 0;
		if (d[h[max]]<d[h[x]])
		{
			poz[h[x]]=max;
			poz[h[max]]=x;
			swap(x,max);
			x=max;
		}
		else return 0;
	}
}
int perc(int x)
{
	int dad=x>>1;
	while (x>1)
	{
		if (d[dad]>d[x])
		{
			poz[h[x]]=dad;
			poz[h[dad]]=x;
			swap(dad,x);
			x=dad;
		}
		else x=1;
	}
	return 0;
}
int main(void)
{
	int min=inf;
	fscanf(f,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(f,"%d%d%d",&x,&y,&c);
		add(x,y,c);
	}
	for (i=1;i<=n;i++)
		d[i]=inf, poz[i]=-1;
	h[1]=1;
	poz[1]=1;
	d[1]=0;
	k=1;
	while (k)
	{
		min=h[1];
		swap(1,k);
		poz[h[1]]=1;
		k--;
		sift(1);
		nod *q=a[min];
		while (q!=NULL)
		{
			if (d[min]+q->d<d[q->y])
			{
				d[q->y]=d[min]+q->d;
				if (poz[q->y]!=-1)
					perc(poz[q->y]);
				else
				{
					h[++k]=q->y;
					poz[q->y]=k;
					perc(k);
				}
			}
			q=q->next;
		}
	}
	for (i=2;i<=n;i++)
	{
		fprintf(g,"%d ",d[i]==inf ? 0:d[i]);
	}
	fprintf(g,"\n");
	fclose(g);
	return 0;
}