#include <bits/stdc++.h>
using namespace std;
int dp[10000][10000],m,n,u,v,w;
void floyd(){
    for(int z=1;z<=n;z++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=min(dp[i][j],dp[i][z]+dp[z][j]);
            }
            
        }
    }
}
void floy(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            i==j? dp[i][j]=0:dp[i][j]=1000000;
        }
    }
}
int main(){
    cin>>n>>m;
    floy();
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        dp[u][v]=min(dp[u][v],w);
        dp[v][u]=min(dp[v][u],w);
    }
    floyd();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}