#include<bits/stdc++.h>
using namespace std;
long long f[101][4501],n,m,x,y,w;
int main(){
	cin>>n>>m;
	memset(f,100000000,sizeof(f));
	for(int i=1;i<=m;i++)cin>>x>>y>>w,f[y][x]=f[x][y]=w;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(k!=i&&k!=j&&i!=j&&f[i][k]+f[k][j]<f[i][j])f[i][j]=f[i][k]+f[k][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)cout<<f[i][j]<<" ";
		cout<<endl;
	}
}