/* RoyFloyd - O(N^3)
D[i][j]= lungimea drumului minim de la i la j
last[i][j] = nodul de pe lantul i-j , imediat inaintea lui j
pentru un intermediar k daca
in loc de i->j fac i->k->j drumul e mai scurt sau i->j nu exista
atunci  D[i][j]=D[i][k]+D[k][j]
        last[i][j]=last[k][j]
*/

#include <fstream>
#define Nmax 110
using namespace std;
ifstream f("royfloyd.in"); ofstream g("royfloyd.out");

int N,M,d[Nmax][Nmax],last[Nmax][Nmax];

void ReadInput()
{
     f>>N;
     for(int i=1;i<=N;++i)
          for(int j=1;j<=N;++j)
               f>>a[i][j];
     for(int i=1;i<=N;++i)
          for(int j=1;j<=N;++j)
          {
               int x,y,c;
               f>>x>>y>>c;
               d[x][y]=d[y][x]=c;
               last[x][y]=x;
               last[y][x]=y;
          }
}

void RoyFloyd()
{
     for(int k=1;k<=N;++k)
          for(int i=1;i<=N;++i)
               for(int j=1;j<=N;++j)
                    if(i!=j && d[i][k]*d[k][j] &&(!d[i][j] || d[i][k]+d[k][j]<d[i][j]))
                    d[i][j]=d[i][k]+d[k][j],last[i][j]=last[k][j];
}

void PrintOutput()
{
     for(int i=1;i<=N;++i,g<<'\n')
          for(int j=1;j<=N;++j)
               g<<d[i][j]<<' ';
}
void Build(int nod,int S)
{
     if(nod==S)
     {
          g<<S<<' ';
          return;
     }
     Build(last[S][nod],S);
     g<<nod<<' ';
}
int main()
{
     ReadInput();
     RoyFloyd();
     //Build(1,6);
     f.close();g.close();
     return 0;
}