#include <bits/stdc++.h>

const int INF = INT_MAX / 2;
const int NMAX = 101;

std::vector<std::vector<int>> D(NMAX, std::vector<int>(NMAX, INF));

int main() {
    freopen("royfloyd.in", "r", stdin);
    freopen("royfloyd.out", "w", stdout);
    
    int n, m;
    std::cin >> n >> m;
    
    while(m--) {
        int x, y, z;
        std::cin >> x >> y >> z;
        D[x][y] = z;
    }
    
    for(int k = 1; k <= n; ++k) {
        D[k][k] = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                D[i][j] = std::min(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }
     
    for(int i = 1; i <= n; ++i, std::cout << '\n')
        for(int j = 1; j <= n; ++j)
            std::cout << (D[i][j] == INF ? -1 : D[i][j]) << ' ';
    
    return 0;
}

/*

SAME ALGORITHM, DIFFERENT ORDER
IJK INSTEAD OF KIJ
BUT IF THE NESTED LOOP RUNS FOR 3 TIMES
IT GIVES THE CORRECT OUTPUT
LOL

#include <iostream>
#include <queue>
#include <climits>

const long long INF = 1e18;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(n + 1, INF));

    for(int i = 1; i <= m; ++i) {
        int x, y, c;
        std::cin >> x >> y >> c;
        dp[x][y] = dp[y][x] = std::min(dp[x][y], 1LL * c);
    }

    std::vector<std::pair<int, int>> querries;

    while(q--) {
        int x, y;
        std::cin >> x >> y;
        querries.push_back( { x, y } );
    }

    for(int t = 3; t >= 1; --t) {
        for(int i = 1; i <= n; ++i) {
            dp[i][i] = 0;
            for(int j = 1; j <= n; ++j)
                for(int k = 1; k <= n; ++k)
                    dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k][j]);
        }
    }

    for(auto querry : querries) {
        int x = querry.first, y = querry.second;
        std::cout << ((dp[x][y] == INF) ? -1 : dp[x][y]) << '\n';
    }
    
    return 0;
}

*/