#include <memory.h>
#include <stdio.h>
#define nmax 50005
#define inf 2000000000
struct arc
{
	long vi,vf,cost;
}e[nmax];

long d[nmax],use[nmax];
int main()
{
	long a,b,c,n,m,i,j,p=1;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=m;i++)
		scanf("%ld %ld %ld",&e[i].vi,&e[i].vf,&e[i].cost);
	for (i=2;i<=n;i++)
		d[i]=inf;
	i=1;
	while (i<n&&p)
	{
		p=0;
		for (j=1;j<=m;j++)
		{
			a=e[j].vi;
			b=e[j].vf;
			c=e[j].cost;
			if (d[b]>d[a]+c)
			{
				d[b]=d[a]+c;
				p=1;
			}
		}
		i++;
	}
	for (i=2;i<=n;i++)
		if (d[i]!=inf) printf("%ld ",d[i]);
		else printf("0 ");
	printf("\n");
	return 0;
}