#include <bits/stdc++.h>
using namespace std;

int n,m,g[101][101],dis[101][101];

void swap(int &a,int &b){
	int temp=a;
	a=b;
	b=temp;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(i==j) g[i][j]=0;
			else g[i][j]=2001;
			
			dis[i][j]=2001;
		}
	
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		if(u<v) swap(u,v);
		g[u][v]=w;
	}
	
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=i;j++)
				dis[i][j]=min(dis[i][j],g[i][k]+g[k][j]);
				
	for(int i=1,x;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<dis[max(i,j)][i+j-max(i,j)];
			if(j!=n)cout<<' ';
		}cout<<endl;
	}
			
	return 0;
}