#include<fstream>
using namespace std;
ifstream in("viteza2.in");
ofstream out("viteza2.out");
const int NMAX = 1000;
const int INFINIT = (1 << 20);

struct drum{
    int lg;
    int dmax;
    int dmin;
};
drum v[NMAX + 5][NMAX + 5];

int n,m;

void read()
{

    in>>n>>m;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
            if(i != j)
                v[i][j].lg = INFINIT;

    int a,b,c;
    for(int i = 1 ; i <= m ; i++){
        in>>a>>b>>c;
        v[a][b].lg = c;
        v[a][b].dmax = c;
        v[a][b].dmin = c;
        v[b][a].lg = c;
        v[b][a].dmax = c;
        v[b][a].dmin = c;
    }
    in.close();
}

void roy_floyd()
{
    for(int k = 1 ; k <= n ; k++)
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= n ; j++)
                if(i != j && i != k && j != k){

                    if(v[i][j].lg > v[i][k].lg + v[k][j].lg && v[i][k].dmax < v[k][j].dmin){
                        v[i][j].lg = v[i][k].lg + v[k][j].lg;
                        v[i][j].dmax = v[k][j].dmax;
                        v[i][j].dmin = v[i][k].dmin;
                    }
                }
}

void afis()
{

    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++)
            if(v[i][j].lg < INFINIT)
                out<<v[i][j].lg<<" ";
            else
                out<<-1<<" ";
        out<<"\n";
    }
}

int main()
{

    read();
    roy_floyd();
    afis();
    return 0;
}