#include<stdio.h>
#define NMAX 1001
#define INF 1000000000
int z[NMAX],q[NMAX*NMAX],d[NMAX],b,c,in,sf,x[NMAX][NMAX],y[NMAX][NMAX],i,j,n,m,k,l,a,s,w[NMAX][NMAX];
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);
		x[a][b]=c;
		y[a][++y[a][0]]=b;
	}
	q[++sf]=1;
	for (i=2;i<=n;i++)
		d[i]=INF;
	in++; z[1] = 1;
	while (in<=sf)
	{
		for (i=1;i<=y[q[in]][0];i++)
			if (d[q[in]]+x[q[in]][y[q[in]][i]]<d[y[q[in]][i]])
			{
				d[y[q[in]][i]]=d[q[in]]+x[q[in]][y[q[in]][i]];
				if (!z[y[q[in]][i]])
				{
					q[++sf]=y[q[in]][i];
					z[y[q[in]][i]]=1;
				}
			}
		z[q[in]]=0;
		in++;
	}
	for (i=2;i<=n;i++)
		if (d[i]!=INF)
			printf("%d ",d[i]);
		else{
			printf("0 ");
			d[i] = 0;
		}
	printf("\n");

	/*fclose(stdin);
	fclose(stdout);
	
	freopen("ccp.txt", "rt", stdin);
	freopen("kkt.out", "w",stdout);
	int www[100000], vf;
	for (i = 2; i <= n; i ++){
		scanf("%d", &vf);
		if (vf != d[i])
			printf("%d %d %d\n", i, vf, d[i]);
	}
	*/
	return 0;
}