//RoyFloyd - O(N^3)
#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)
          {
               int x,y,c;
               f>>x>>y>>c;
               d[x][y]=c , last[x][y]=x;
               d[y][x]=c , 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();
     PrintOutput();
     Build(1,6);
     f.close();g.close();
     return 0;
}