#include<iostream>
#include<fstream>
using namespace std;
ifstream in("royfloyd.in");
ofstream out("royfloyd.out");
#define inf 2000000
int n,c[101][101],m;
void citire(){
	int i,x,y,z;
	in>>n>>m;
	for(i=1;i<=m;i++){
		in>>x>>y>>z;
		c[x][y]=z;
	}
}
	void completare(){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(!c[i][j])c[i][j]=inf;
	}
	void RF(){
		int i,j,k;
		for(k=1;k<n;k++)
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
					if(i!=j&&k!=i&&k!=j){
						int aux=c[i][k]+c[k][j];
						if(aux<c[i][j])c[i][j]=aux;
					}
					
	}
	
	int main(){
		citire();
		completare();
		RF();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)
				if(c[i][j]<inf)
					cout<<c[i][j]<<" ";
				else cout<<0<<" ";
				cout<<endl;
		}
		return 0;
	}