#include <iostream>
#include <limits.h>
using namespace std;
int gmd[101][101],n,l;
int main()
{
	cin >> n >> l;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			if(i!=j)
				gmd[i][j]=1009999999;
		}
	}
	for(int i=1; i<=l; i++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		if(c<=gmd[a][b]||gmd[a][b]==0)
		    gmd[a][b]=gmd[b][a]=c;
	}
	for(int k=1; k<=n; k++)
	{
		for(int i=1; i<=n; i++)
		{
			for(int j=1; j<=n; j++)
			{
			    if(i==k||i==j||j==k)continue;
				if(gmd[i][j]>gmd[i][k]+gmd[k][j])gmd[i][j]=gmd[j][i]=gmd[i][k]+gmd[k][j];
			}
		}
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			cout << gmd[i][j] <<" ";
		}
		cout<< endl;
	}
	return 0;
}