#include <bits/stdc++.h>
#define INF 0x3F3F3F3F

using namespace std;

ifstream f("royfloyd.in");
ofstream g("royfloyd.out");

int n,m,i,j,k,x,y,cost,mat[101][101];
bool matArc[101][101];

int main()
{
    ios::sync_with_stdio(0);
    f >> n >> m;
    while(m --)
    {
        f >> x >> y >> cost;
        mat[x][y] = cost;
        matArc[x][y] = 1; // Poate costul este *zero
    }
    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            if(i != j && !matArc[i][j])
                mat[i][j] = INF;
    for(k = 1; k <= n; ++ k)
        for(i = 1; i <= n; ++ i)
            for(j = 1; j <= n; ++ j)
                mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
    for(i = 1; i <= n; ++ i, g << '\n')
        for(j = 1; j <= n; ++ j)
            if(mat[i][j] == INF)
                g << -1 << ' ';
            else
                g << mat[i][j] << ' ';
}