//QWQ
/*
    多源最短路   Floyed
    memset 0x3f       自己距离为0 
	邻接矩阵存图   重边取小，自环为0 
	Floyed求最短路   O(n^3) 
	输出    a（ i，j ） 
*/ 
#include<bits/stdc++.h>
using namespace std;
int const N=105,M=4505;
int a[N][N];
int n,m;
int main()
{
	memset(a,0x3f,sizeof a);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int z,b,c;
		cin>>z>>b>>c;
		a[z][b]=min(a[z][b],c);
		a[b][z]=a[z][b];
	}
	for(int i=1;i<=n;i++)  a[i][i]=0;
	for(int k=1;k<=n;k++)
	   for(int i=1;i<=n;i++)
	        for(int j=1;j<=n;j++)
	            a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)   cout<<a[i][j]<<" ";
		cout<<'\n';
	}
	return 0;
 }