#include<cstdio>
#include<limits.h>
using namespace std;

int dist[1000][1000],n,m;

void init(){
    int from,to,weight;

    scanf("%d %d",&n,&m);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist[i][j]=INT_MAX;
        }
        dist[i][i]=0;
    }

    for(int i=0;i<m;i++){
        scanf("%d %d %d",&from,&to,&weight);
        dist[from][to]=weight;
    }
}

void floyd(){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k]+dist[k][j]<dist[i][j]){///check for INT_MAX because if we add those the number will get negative and update values
                    dist[i][j]=dist[i][k]+dist[k][j];
                }
            }
        }
    }
}

void print(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%d ",dist[i][j]);
        }
        printf("\n");
    }
}


int main(){
    init();
    floyd();
    print();
}