#include<iostream>
#include<cstring>
using namespace std;
int n,m;
int e[110][110];
int main(){
    cin>>n>>m;
    memset(e,1e8,sizeof(e));
    for(int i=1;i<=n;i++){
        e[i][i]=0;
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u][v]=min(e[u][v],w);
        e[v][u]=min(e[v][u],w);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                min(e[i][j],e[i][k]+e[k][j]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<e[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}