#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
long a[101][101];
int main()
{
	memset(a,0x3f,sizeof(a));
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		long w;
		cin>>x>>y>>w;
		a[x][y]=w;
		a[y][x]=w;
		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<<endl;
   }
	return 0;
}

0; }