#include<stdio.h>
#define N_ 50005
#define M_ 250005
#define OO 1<<30
int *a[N_],*c[N_],x[M_],d[N_],y[M_],h[M_],N,M;
int poz[M_],k;
void swap(int &x,int &y)
{
	int aux=x;
	x=y;
	y=aux;
}
void citire()
{
	scanf("%d%d",&N,&M);
	for (int i=1; i<=M; ++i)
	{
		scanf("%d%d%d",&x[i],&poz[i],&h[i]);
		++d[x[i]];
	}
	for (int i=1; i<=N; ++i)
	{
		a[i]=new int [1+d[i]];
		c[i]=new int [1+d[i]];
		a[i][0]=c[i][0]=0;
	}
	for (int i=1; i<=N; ++i)
	{
		a[x[i]][++a[x[i]][0]]=poz[i];
		c[x[i]][++c[x[i]][0]]=h[i];
	}
}
void cobor(int y)
{
	int fiu=y;
	while (true)
	{
		if ((y<<1)<=k && d[h[y<<1]]<d[h[y]])
		    fiu=y<<1;
		if ((y<<1)+1<=k && d[h[(y<<1)+1]]<d[h[fiu]])
			fiu=(y<<1)+1;
		if (y==fiu)
			return;
		poz[h[fiu]]=y;
		poz[h[y]]=fiu;
		swap(h[fiu],h[y]);
		y=fiu;
	}
}
void urc(int y)
{
	int key=h[y];
	while (y-1 && key<h[y>>1])
	{
		poz[h[y>>1]]=y;
		h[y]=h[y>>1];
		y>>=1;
	}
	poz[key]=y;
	h[y]=key;
}
void dijkstra()
{
	for (int i=1; i<=N; ++i)
		d[i]=OO,h[i]=0,poz[i]=0;
	h[++k]=1;
	d[1]=0;
	poz[1]=k;
	while (k)
	{
		int x=h[1];
		h[1]=h[k];
		poz[h[k]]=0;
		poz[h[1]]=1;
		--k;
		cobor(1);
		for (int i=1; i<=a[x][0]; ++i)
		{
			if (d[a[x][i]]>d[x]+c[x][i])
			{
				d[a[x][i]]=d[x]+c[x][i];
				if (poz[a[x][i]])
					urc(poz[a[x][i]]);
				else
				{
					h[++k]=a[x][i];
					poz[a[x][i]]=k;
					urc(k);
				}
			}
		}
	}
}
void afis()
{
	for (int i=2; i<=N; ++i)
		printf("%d ",(d[i]==OO)?0:d[i]);
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("disjkstra.out","w",stdout);
	citire();
	dijkstra();
	afis();
	return 0;
}