#include<bits/stdc++.h>
using namespace std;
#define int long long
int mp[200][200];
signed main(){
	memset(mp,0,sizeof(mp));
	int n,m;
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%lld %lld ",&u,&v);
		scanf("%lld",&mp[u][v]);
		mp[v][u]=mp[u][v];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				if(mp[j][i]+mp[i][k]<mp[j][k]||!mp[j][k]&&j!=k){
					mp[j][k]=mp[j][i]+mp[i][k];
					mp[k][j]=mp[j][k];
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			printf("%lld",mp[i][j]);
			putchar(' ');
		}
		putchar('\n');
	}
	return 0;
}