#include<cstdio>
#define N 50001
#define M 250001
#define INF 2000000000
int *a[N],*a1[N],n,m,x[M],y[M],c[M],d[N],nr[N];
bool viz[N];
void citire()
{
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d%d",&x[i],&y[i],&c[i]);
		++d[x[i]];
	}
	for (int i=1; i<=n; ++i)
	{
		a[i]=new int [1+d[i]];
		a1[i]=new int [1+d[i]];
		a[i][0]=a1[i][0]=0;
	}
	for (int i=1; i<=m; ++i)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
		a1[x[i]][++a1[x[i]][0]]=c[i];
	}
}
void bf_s(int x0)
{
	int p=0,u=0, coada[N],x,y;
	for (int i=1; i<=n; ++i)
		d[i]=INF;
	viz[x0]=true;
	d[x0]=0;
	nr[x0]=1;
	coada[u++]=x0;
	while (u!=p)
	{
		x=coada[p++];
		viz[x]=false;
		for (int i=1; i<=a[x][0]; ++i)
		{
			y=a[x][i];
			if (d[x]+a1[x][i]<d[y])
			{
				d[y]=d[x]+a1[x][i];
				nr[y]=nr[x];
			}
			else
				if (d[x]+a1[x][i]==d[y])
					nr[y]+=nr[x];
			if (!viz[y])
			{
				viz[y]=true;
				coada[u++]=y;
			}
		}
	}
}
void afis()
{
	for (int i=2; i<=n; ++i)
		printf("%d ",(d[i]!=INF)? d[i] : 0);
	/*printf("\n");
	for (int i=1; i<=n; ++i)
		printf("%d ",nr[i]);*/
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	bf_s(1);
	afis();
	return 0;
}