#include<fstream>
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");
int n,m,a[50][50];
void citire()
{   f>>m;
    int x,y,c;
    for(int i=1;i<=m;i++)
    {   f>>x>>y>>c;
        a[x][y]=c;
    }
}
void init()
{   for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                a[i][j]=1000000000;
}
void drumuri_R_F()
{   for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][k]+a[k][j]<a[i][j]) a[i][j]=a[i][k]+a[k][j];

}
void afis()
{   for(int i=1;i<=n;i++)
    {   for(int j=1;j<=n;j++)
            g<<a[i][j]<<" ";
        g<<'\n';
    }
}
int main()
{   f>>n;
    init();
    citire();
    afis();
    drumuri_R_F();
    afis();
    return 0;
}