#include<bits/stdc++.h>
using namespace std;
long long n,m,q,s,a,b,w,dp[205][205];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>w;
		dp[a][b]=max(dp[a][b],w);
		dp[b][a]=max(dp[b][a],w);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
    for(int i=1;i<=n;cout<<"\n",i++)
        for(int j=1;j<=n;j++)
            cout<<dp[j][i]<<" ";
	return 0;
}