#include<bits/stdc++.h>
using namespace std;
#define mx 10000
int cost[mx][mx],adj[mx][mx],dis[mx],n,e,i,j,c,k;
void floyed()
{
    for(k=0;k<n;k++){
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(cost[i][j]>cost[i][k]+cost[k][j]){
                    cost[i][j]=cost[i][k]+cost[k][j];
                }
            }
        }
    }
}
int main()
{
    cin>>n>>e;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(i==j){
                cost[i][j]=0;
            }
            else cost[i][j]=100000;
        }
    }
    for(i=0;i<e;i++){
        int n1,n2;
        cin>>n1>>n2>>c;
        cost[n1][n2]=c;
        cost[n2][n1]=c;
    }
    floyed();
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            cout<<cost[i][j]<<" ";
        }
        cout<<endl;
    }
}