#include<cstdio>
using namespace std;
int ul,i,j,mini,n,m,x,y,c,a[1001][1001],b[1002],ap[1002];
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		a[i][j]=-1;
for(i=1;i<=m;i++)
{
	scanf("%d",&x);
	scanf("%d",&y);
	scanf("%d",&c);
	a[x][y]=c;
}
ul=1;
ap[ul]=1;
for(i=2;i<=n;i++)
	b[i]=-1;
while(1)
{
	for(i=1;i<=n;i++)
		if(a[ul][i]!=-1&&ul!=i&&((b[i]!=-1&&b[i]>b[ul]+a[ul][i])||b[i]==-1))
			b[i]=a[ul][i]+b[ul];
	mini=1000000;
	for(i=1;i<=n;i++)
		if(ap[i]==0&&b[i]!=-1&&b[i]<mini)
		{
			mini=b[i];
			ul=i;
		}
	if(mini==1000000) break;
	ap[ul]=1;
}
for(i=2;i<=n;i++)
{
	if(b[i]==-1) printf("0 ");
	else printf("%d ",b[i]);
}
return 0;
}