#include <cstdio>

using namespace std;

int mat[1001][1001];

int main()
{
    freopen( "royfloyd.in", "r", stdin );
    freopen( "royfloyd.out", "w",stdout );
    int n, m, i, x, y, z;
    scanf( "%d%d", &n, &m );
    for( x=1; x<=n; ++x )
        for( y=1; y<=n; ++y )
            if( x!=y )mat[x][y]=0x3f3f3f3f;
    for( i=1; i<=m; ++i )
    {
        scanf( "%d%d%d", &x, &y, &z );
        mat[x][y]=z;
    }

    for( i=1; i<=n; ++i )
        for( x=1; x<=n; ++x )
            for( y=1; y<=n; ++y )
                if( x!=y && x!=i && i!=y && mat[x][i]+mat[i][y]<mat[x][y] )
                    mat[x][y]=mat[x][i]+mat[i][y];

    for( x=1; x<=n; ++x, printf("\n") )
        for( y=1; y<=n; ++y )
            if( mat[x][y]==0x3f3f3f3f )printf( "inf " );
            else printf( "%d ", mat[x][y] );
    return 0;
}