#include<stdio.h>
int a[10000][10000],s[10000];
int main()
{
	
	int n,m,i,j,d[10000],x,c,y,poz,min;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				a[i][j]=0;
			else
				a[i][j]=1000000000;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		a[x][y]=c;
	}
	for(i=1;i<=n;i++)
		d[i]=a[1][i];
	for(i=1;i<=n-1;i++)
	{
		min=1000000000;
		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(d[j]>d[poz]+a[poz][j]&&s[j]==0)
				d[j]=d[poz]+a[poz][j];
	}
	for(i=2;i<=n;i++)
		if(d[i]==1000000000)
			printf("0 ");
		else
		printf("%d ",d[i]);
	return 0;
}