# include <bits/stdc++.h>

using namespace std;
const int N=1e2+5;
const int INF=0x3f3f3f3f;
int u,v,w,dst[N][N],n,m;
int main(){
	cin>>n>>m;
	memset(dst,INF,sizeof(dst));
	for(int i = 1;i<=m;i++){
		cin>>u>>v>>w;
		dst[u][v]=min(dst[u][v],w);
		dst[v][u]=min(dst[v][u],w);
	}
	for(int i = 1;i<=n;i++)dst[i][i]=0;
	for(int k = 1;k<=n;k++)
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=n;j++)
				dst[i][j]=min(dst[i][j],dst[i][k]+dst[k][j]);
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++)
			cout<<dst[i][j]<<' ';
		cout<<'\n';
	}
	return 0;
}