#include<stdio.h>
const int maxn=50001;
int A[1000][1000],S[1000],D[1000],n,m,i,j,k,a,b,c,min,poz;
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%D",&a,&b,&c);
		A[a][b]=c;
	}
	for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			       if(A[i][j]==0)
					   A[i][j]=1001;
	S[1]=1;
	for(i=2;i<=n;i++)
		D[i]=A[1][i];
	for(i=1;i<=n-1;i++)
	{
		min=1001;
		for(j=1;j<=n;j++)
			if(S[j]==0)
				if(D[j]<min)
				{
					min=D[j];
					poz=j;
				}
	S[poz]=1;
	for(j=1;j<=n;j++)
		if(S[j]==0)
			if(D[j]>D[poz]+A[poz][j])
				D[j]=D[poz]+A[poz][j];
	}
	for(j=2;j<=n;j++)
		printf("%d ",D[j]);
	return 0;
}