#include <stdio.h>

const int inf = 1e9;

int main() {
    int n,m,i,j,k;
    FILE*file1 = fopen("pathsg.in","r");
    FILE*file2 = fopen("pathsg.out", "w");
    fscanf(file1,"%d %d", &n, &m);
    int distance[n+1][n+1];
    for (i=1; i <=n; i++){
        for(j=1; j<=n; j++){
            distance[i][j] = inf;
        }
    }
    for(i=1; i<=m; i++){
        int start, finish, weight;
        fscanf(file1,"%d %d %d", &start, &finish, &weight);
        distance[start][finish] = weight;
    }
    for (i=1; i<=n; i++){
        distance[i][i] = 0;
    }
    for(k=1; k<= n; k++)
        for(i=1; i<= n; i++)
            for(j=1; j <=n; j++)
                if (distance[i][k] != inf && distance[k][j] != inf && distance[i][k] + distance[k][j] < distance[i][j])
                    distance[i][j] = distance[i][k] + distance[k][j];
    for (i=1; i<= n; i++){
        for (j=1; j<= n; j++){
            fprintf(file2, "%d ", distance[i][j]);
        }
        fprintf(file2, "\n");
    }
    return 0;
}