#include<bits/stdc++.h>
using namespace std;
int f[1001][1001];
int n,x,y,m,s,e;
int main()
{cin>>n>>m;
for (int i=1;i<=n;i++)
{
	for (int j=1;j<=n;j++)
	{
		f[i][j]=9999999;
	}
}
for (int i=1;i<=m;i++)
{cin>>x>>y>>f[x][y];}

for (int k=1;k<=n;k++)
{
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if (i!=j&&j!=k&&i!=k&&f[i][j]>f[i][k]+f[k][j])
			{
				f[i][j]=f[i][k]+f[k][j];
			}
		}
	}
 } 
 for (int i=1;i<=n;i++)
 {
 	for (int j=1;j<=n;j++)
 	{
 		cout<<f[i][j]<<" ";
	 }
	 cout<<"\n";
 }
 
 return 0;}