#include<stdio.h>
#include<string.h>
#define inf 2000000000
#define NMAX 50005
#define MMAX 250005
int l,a,b,c,i,j,n,m,p,d[NMAX];
char ss[32],cc;
struct kkt
{
    int X,Y,Z;
} x[MMAX];
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d%c",&n,&m,&cc);
	for (i=1;i<=m;i++)
{
		fgets(ss,32,stdin);
        l=strlen(ss)-1;
        a=b=c=j=0;
        while (ss[j]!=' ')
        	a=a*10+ss[j++]-48;

        j++;
        while (ss[j]!=' ')
        	b=b*10+ss[j++]-48;

        j++;
        while (j<l)
        	c=c*10+ss[j++]-48;
	x[i].X=a;
	x[i].Y=b;
	x[i].Z=c;
//		scanf("%d%d%d",&x[i],&y[i],&z[i]);
}
	for (i=2;i<=n;i++)
		d[i]=inf;
	p=1;
	i=1;
	while (i<n&&p)
	{
		p=0;
		for (j=1;j<=m;++j)
		{
			a=x[j].X;
			b=x[j].Y;
			c=x[j].Z;
			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("%d ",d[i]);
		else
			printf("0 ");
	printf("\n");
	return 0;
}