#include  < cstdio >
#include  < cstring >

using namespace std;

#define MAXN  100

long f[MAXN + 1 ][MAXN + 1 ];
long n;
long from,to;
const long maxn = 214748364 ;

void ini( void )
{
     freopen( " shortpath.in " ,  " r " ,stdin);
     freopen( " shortpath.out " ,  " w " ,stdout);
     
     memset(f,  0 ,sizeof(f));
     
     scanf( " %ld " , & n);
     
      long  i, j;
      for (i = 1 ; i <= n; i ++ )
           for (j = 1 ; j <= n; j ++ )
              scanf( " %ld " ,  & f[i][j]);
     
     scanf( " %ld %ld " ,  & from,  & to);
      return ;
}

long  dijkstra( void )
{
      long  dist[MAXN  +   1 ];
     bool flag[MAXN  +   1 ];
     
      long  i, j;
      long  mins, mini;
     
     memset(dist,  0 , sizeof(dist));
     memset(flag,  0 , sizeof(flag));
     
      for (i = 1 ; i <= n; i ++ )
      {
              dist[i]  =  maxn;
               if  (f[from][i]  !=   0 )
                 dist[i]  =  f[from][i];
     }
     
     dist[from]  =   0 ;
     flag[from]  =   true ;
     
      for (i = 1 ; i < n; i ++ )
      {
          mins  =  maxn;
          for (j = 1 ; j <= n; j ++ )
               if  (dist[j]  <  mins  &&   ! flag[j])
                 {
                     mins  =  dist[j];
                     mini  =  j;
                    }
              
          flag[mini] = true ;
              
           for (j = 1 ;j <= n;j ++ )
               if (dist[j] > dist[mini] + f[mini][j] && f[mini][j] != 0 )
                  dist[j] = dist[mini] + f[mini][j];
     }
      return  dist[to];
}

long spfa( void )
{
      long  q[ 3   *  MAXN  +   1 ];
      long  head, tail;
      long  dist[MAXN  +   1 ];
      long  flag[MAXN  +   1 ];
     
     memset(q,  0 , sizeof(q));
     memset(dist,  0 , sizeof(dist));
     memset(flag,  0 , sizeof(flag));
     
     memset(flag,  0 , sizeof(flag));
     
      long  i, j;
     head  =   0 ; tail  =   0 ;
     tail ++ ;
     q[tail]  =  from;
     flag[from]  =   true ;
      long  now, tt;
     
       for (i = 1 ; i <= n; i ++ )
              dist[i]  =  maxn;
     
     dist[from]  =   0 ;
     
      while (head  <  tail)
      {
                head ++ ;
                now  =  q[head];
                flag[now]  =   false ;
                
                 for (i = 1 ; i <= n; i ++ )
                          if  (f[now][i])
                          {
                                        if  (dist[i]  >  dist[now]  +  f[now][i])
                                        {
                                                   dist[i]  =  dist[now]  +  f[now][i];
                                                    if  ( ! flag[i])
                                                    {
                                                             flag[i]  =   true ;
                                                             tail ++ ;
                                                             q[tail]  =  i;
                                                   }
                                       }
                         }
                
     }
      return  dist[to];
     
}

long  floyd( void )
{
      long  i, j, k;
     
      long  dist[MAXN  +   1 ][MAXN  +   1 ];
     
      for (i = 1 ; i <= n; i ++ )
           for (j = 1 ; j <= n; j ++ )
                    if  (f[i][j]  !=   0 )
                      dist[i][j]  =  f[i][j];
                    else
                       dist[i][j]  =  maxn;
                       
     for (k = 1 ; k <= n; k ++ )
              for (i = 1 ; i <= n; i ++ )
                       for (j = 1 ; j <= n; j ++ )
                                if  (dist[i][j]  >  dist[i][k]  +  dist[k][j])
                                   dist[i][j]  =  dist[i][k]  +  dist[k][j];    
     
      return  dist[from][to];
}


int  main( void )
{
    ini();
    printf( " %ld\n " , dijkstra());
    printf( " %ld\n " , spfa());
    printf( " %ld\n " , floyd());
     return   0 ;
}