#include<stdio.h>
#define N 50005
#define inf 1<<30
struct graf
{
	int exp,dest,cost;
};
int n,m,d[N];
graf a[N];
void bellman_ford()
{
	int i,j,newdist;
	d[1]=0;
	for(i=0; i<n; i++)
	{
		for(j=0; j<m; j++)
		{
			if(d[a[j].exp]!=inf)
			{
				newdist=d[a[j].exp]+a[j].cost;
				if(newdist<d[a[j].dest])
					d[a[j].dest]=newdist;
			}
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int i;
	scanf("%d%d",&n,&m);
	for(i=0; i<m; i++)
		scanf("%d%d%d",&a[i].exp,&a[i].dest,&a[i].cost);
	for(i=1; i<=n; i++)
		d[i]=inf;
	bellman_ford();
	for(i=2; i<n; i++)
		printf("%d ",d[i]==inf ? 0 : d[i]);
	printf("%d\n",d[n]==inf ? 0 : d[n]);
	return 0;
}