#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
const int N=105;
int n,m,k,s,t,T,x,f[N][N];

int main(){
	cin>>n>>m;
	memset(f,0x3f,sizeof(f));
	for (int i=1;i<=n;++i) f[i][i]=0;
	for (int i=1;i<=m;++i){
		cin>>s>>t>>k;
		f[s][t]=min(f[s][t],k);
		f[t][s]=min(f[t][s],k);
	}	
	for (int k=1;k<=n;++k)
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				f[i][j]=min(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";
	}
}