#include<stdio.h>
#define N 5000
int n,m,a[N][N],i,j,x,y,l,d[N],c[N+N],ic,sf;
void read()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
		{
			scanf("%d%d%d",&l,&x,&y);
			a[x][y]=a[y][x]=l;
		}
	for(i=1;i<=n;++i)
		d[i]=100000;
}
void parcurgere()
{
	int x;
	ic=sf=1;
	c[ic]=1;
	d[1]=0;
	while(ic<=sf)
	{
		x=c[ic++];
		for(i=2;i<=n;++i)
			if(a[x][i]&&d[i]>a[x][i]+d[x])
			{
				c[sf++]=i;
				d[i]=a[x][i]+d[x];
			}
		//ic++;
	}
	for(i=1;i<n;++i)
		printf("%d ",d[i]);
	printf("%d\n",d[n]);
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	parcurgere();
	return 0;
}