#include"stdio.h"
#include<algorithm>

const int N = 110;
int n,m,dis[N][N];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
	{
		for(int j=1;j<=n;j++)
			dis[i][j]=0x3f3f3f3f;
		dis[i][i]=0;
	}
	int u,v,w;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		dis[u][v]=std::min(dis[u][v],w);
		dis[v][u]=std::min(dis[v][u],w);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if(dis[i][j]>dis[i][k]+dis[k][j])
					dis[i][j]=dis[i][k]+dis[k][j];
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			printf("%d ",dis[i][j]);
		printf("\n");
	}
	return 0;
}