#include<iostream>

#include<math.h>

#include<stdio.h>

using namespace std;

//long long ct=0;

//long long arr[1000]={0};

int e[100][100];//存图的数组

int n=0,m=0;

const int inf=99999;

void floyd()

{int k,i,j;

	for(k=1;k<=n;k++)

	{

		for(i=1;i<=n;i++)

		{

			for(j=1;j<=n;j++)

			{

				if(e[i][j]>(e[i][k]+e[k][j]))

				{

					e[i][j]=e[i][k]+e[k][j];

				}

			}

		}

	}

}

int main()

{

	cin>>n>>m;

	for(int i=1;i<=n;i++)// 初始化各个点为inf

	{

		for(int j=1;j<=n;j++)//

		{

			if(i==j)

			{

				e[i][j]=0;

			}

			else

			  e[i][j]=inf;

		}

	}

   for(int i=1;i<=m;i++)//读入m条边

   {                     //有向图

	   int a,b;

	   cin>>a>>b;

	   cin>>e[a][b];

	  // e[b][a]=e[a][b];

   }

  floyd();

  for(int i=1;i<=n;i++)

  {

	 for(int j=1;j<=n;j++)

	 {

		 cout<<e[i][j]<<" ";

	 }

	 cout<<endl;

  }

	return 0;

}