#include<stdio.h>
#define N 1000
#define oo 32000

int n,m,x,y,i,j,nod_cur,viz[N],coada[N],d[N],vf,cost;
int a[N][N];

void bellman(int nod);

int main()
{
		freopen("dijkstra.in","r",stdin);
		freopen("dijkstra.out","w",stdout);

		scanf("%d%d%d",&n,&m);

		vf = 1;

		for(i = 1; i <=m; i++)
			{
			scanf("%d %d %d",&x,&y,&cost);
			a[x][y] = cost;
			}

		bellman(vf);

		for(i=2; i<= n; i++)
			printf("%d ",d[i]);

		return 0;
}

void bellman(int nod)
{
	int prim, ultim;

	viz[nod] = 1;
	prim = ultim = 1;
	coada[prim] = nod;

	for(i = 1; i <= n; i++)
		d[i] = oo;

	d[nod] = 0;
	while(prim <= ultim)
	{
		nod_cur = coada[prim];
		for(i = 1; i <= n; i++)
			if(a[nod_cur][i] !=0)
			 if(d[nod_cur] + a[nod_cur][i] < d[i])
			 {
				d[i] = d[nod_cur] + a[nod_cur][i];
				if(viz[i] == 0)
				{
					coada[++ultim] = i;
					viz[i] = 1;
				}
			}
		prim++;
	}
}