#include<iostream>
#include<fstream>

using namespace std;

int main() {
    //ifstream fin("pathmgep.in");
    //ofstream gaw("pathmgep.out");
    long n, m;
    cin >> n >> m;
    long Matrix[n][n];
    /*long d[n];
    bool Mark[n];
    d[s - 1] = 0;
    Mark[0] = true;
    for (i = 0; i < n; i++) Mark[i] = false;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            cin >> Matrix[i][j];
            if (Matrix[i][j] == -1)  Matrix[i][j] = 2000000000;
        }
    }
    for (i = 0; i < n; i++){
        v = -1;
        for (j = 0; j < n; j++){
            if ((not Mark[j]) and ((v == -1) or (d[v] > d[j]))) v = j;
        }
        Mark[v] = true;
        for (k = 0; k < n; k++){
            if (d[k] > (d[v] + Matrix[v][k])) d[k] = (d[v] + Matrix[v][k]);
        }
    }*/
    long d[n][n];
    for (long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) d[i][j] = 0;
    }
    for (long i = 0; i < m; i++) {
        long k, j, v;
        cin >> k >> j >> v;
        d[k][j] = v;
            //if (Matrix[k][j] == -1)  Matrix[k][j] = 2000000000;
            //d[k][j] = Matrix[k][j];
    }
    for (long i = 1; i < n + 1; i++){
        for (long j = 0; j < n; j++){
            for (long k = 0; k < n; k++){
                if (d[j][k] > d[j][i - 1] + d[i - 1][k]) d[j][k] = d[j][i - 1] + d[i - 1][k];
            }
        }
    }
    //if (d[s - 1][f - 1] == 2000000000) d[s - 1][f - 1] = -1;
    //gaw << d[s - 1][f - 1] << endl;
    for (long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) cout << d[i][j] << ' ';
        cout << endl;
    }
}