#include <bits/stdc++.h>
using namespace std;
//int f[10000][10000];
int main(){
	int n,m;
	cin>>n>>m;
	int f[n][n]={};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=10000;
			if(i==j){
				f[i][j]=0;
			}
		}
	}
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		f[a][b]=c;
		f[b][a]=c;
	}
	for (int k = 1; k <= n; k++) {
  		for (int x = 1; x <= n; x++) {
    		for (int y = 1; y <= n; y++) {
      			f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
    			}
  			}
		} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<f[i][j]<<" ";
		}
		cout<<endl;
	}
}