#include <stdio.h>
#define inf 10005

struct nod{
			int v,ct;
			}*c[50005];

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

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d", &n, &m);
	for (i=1;i<=n;i++)
		{
			c[i]=(nod*)realloc(c[i],sizeof(nod));
			c[i][0].v=0;
		}
	for (i=1;i<=m;i++)
		{
			scanf("%d %d %d", &x, &y, &ct);
			c[x][0].v++;
			c[x]=(nod*)realloc(c[x],(c[x][0].v+1)*sizeof(nod));
			c[x][c[x][0]].v=y;
			c[x][c[x][0]].ct=ct;
		}
	for (i=1;i<=n;i++)
		if (i!=1)
	 for (j=1;j<=c[1][0].v;j++)
		 if (c[1][j].v==i)
			d[i]=c[1][j].ct;
	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])
					for (l=1;l<=c[y][0].v;l++)
						if (c[y][l].v==y)
							d[i]=min+c[y][l].ct;
		}
	for (i=2;i<=n;i++)
		printf("%d ", d[i]);
	return 0;
}