#include <stdio.h>
#define N 1000
int x,y,c,m,n;
short int a[N][N];
int main()
{
	freopen("dijkstra.in", "r",stdin);
	freopen("dijkstra.out", "w",stdout);
	scanf("%d%d", &n,&m);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		{
			scanf("%d%d%d", &y,&x,&c);
			a[y][x]=c;
		}	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(!a[i][j])
				a[i][j]=N*N;
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				if (a[i][k]&&a[k][j]&&(a[i][j]>a[i][k]+a[k][j]|| !a[i][j])&&i!=j)  
                    a[i][j]=a[i][k]+a[k][j];  
	for(int j=2;j<=n;++j)
		printf("%d ",a[1][j]);
	printf("\n");
	return 0;
}