#include <fstream>
#define inf 0x3f3f3f3f

using namespace std;

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

int n, m;
int c[105][105];

void initializare()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            if(i==j)
                continue;
            c[i][j]=inf;
        }
}

void royfloyd()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
        {
            if(i==k)
                continue;
            for(int j=1; j<=n; j++)
            {
                if(i==j || j==k)
                    continue;
                if(c[i][j]>c[i][k]+c[k][j])
                    c[i][j]=c[i][k]+c[k][j];
            }
        }
}

int trans(int x)
{
    if(x==inf)
        return -1;
    return x;
}

int main()
{
    f>>n>>m;
    initializare();
    for(int i=1; i<=m; i++)
    {
        int x, y, cost;
        f>>x>>y>>cost;
        c[x][y]=cost;
    }
    royfloyd();
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            g<<trans(c[i][j])<<' ';
        g<<'\n';
    }

    return 0;
}