#include<stdio.h>
int v[10000][3],c[10000],i,x,y,j,ok; 
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&x, &y);
	for(i=1;i<=y;i++)scanf("%d %d %d",&v[i][0],&v[i][1],&v[i][2]);
	for(i=2;i<=x;i++)c[i]=2000000000;
	for(i=1;i<=x;i++)
	{
		for(j=1;j<=y;j++)
			if(v[j][0]==i)
				if(v[j][2]+c[i]<c[v[j][1]])
					c[v[j][1]]=v[j][2]+c[i],ok=0;
	}
	for(i=2;i<=x;i++)printf("%d ",c[i]);
	return 0;
}