#include <stdio.h>
#define inf 10005

int n,m,i,j,x,y,min,c[5005][5005],ct,d[50005],viz[50005];

int main()
{
	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++)
				c[i][j]=inf;
			c[i][i]=0;
		}
	for (i=1;i<=m;i++)
		{
			scanf("%d %d %d", &x, &y, &ct);
			c[x][y]=ct;
		}
	for (i=1;i<=n;i++)
		if (i!=1)
			d[i]=c[1][i];
	viz[1]=1;
	for (j=1;j<n;j++)
		{
			min=inf;
			for (i=1;i<=n;i++)
				if (!viz[i] && min>d[i])
					{
						min=d[i];
						y=i;
					}
			viz[y]=1;
			for (i=1;i<=n;i++)
				if (!viz[i] && d[i]>min+c[y][i])
							d[i]=min+c[y][i];
		}
	for (i=2;i<=n;i++)
		printf("%d ", d[i]);
	return 0;
}