//Bellman - Ford bc

#include <stdio.h>
#define nmax 50001
#define mmax 250001

struct muchie {int x,y,cost;} a[mmax];
int c[nmax],n,m;

int main()
{
	int i,ok=0;
	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[i].x,&a[i].y,&a[i].cost);
		if(a[i].x==1)
			c[a[i].y]=a[i].cost;
	}
	for(i=2;i<=n;i++)
		if(c[i]==0)
			c[i]=mmax;
	while(ok==0)
	{
		ok=1;
		for(int i=1;i<=m;i++)
			if(c[a[i].y]>c[a[i].x]+a[i].cost)
			{
				c[a[i].y]=c[a[i].x]+a[i].cost;
				ok=0;
			}
	}
	for(i=2;i<=n;i++)
	{
		if(c[i]==mmax)
			printf("0 ");
		else
			printf("%d ",c[i]);
	}
	return 0;
}