#include <iostream>
#include <cmath>

using namespace std;

#define INF 9999999

int** C; // Optimums-Matrix
int** d; // Distanzen zwischen den Städten
int iN;  // Anzahl Städte

int NumberOfSetBits(int i); // Zählt die gesetzten Bits in einem Integer

int main()
{
   /** Anzahl Städte einlesen **/
   scanf("%i",&iN);

   /** Initialisieren **/
   C = new int*[iN+1];         // n Zahlen ohne 0 -> iN+1
   for(int i=2; i <= iN; i++)  // Bis und mit iN ohne 0
      C[i] = new int[(1<<iN)]; // 2^iN ohne 0, jedoch ist 2^iN bereits der komplette Weg (7 = 111 oder 15 = 1111); 1<<x = 2^x

   d = new int*[iN+1];        // n Zahlen ohne 0
   for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0
      d[i] = new int[iN+1];   // n Zahlen ohne 0

   /** Eingabe **/
   for(int i=1; i <= iN; i++)    // Bis und mit iN ohne 0
      for(int j=1; j <= iN; j++) // Bis und mit iN ohne 0
      {
         scanf("%i", &d[i][j]);   // Distanzen einlesen
      }

   /*********************************************
    *                Algorithmus                *
    *********************************************/

   /** Initialisiere alle mit Mächtigkeitszahl 2 in C **/
   for(int k=2; k <= iN; k++) // Ohne 0 & 1 für k, bis und mit iN
   {
         C[k][1^(1<<(k-1))] = d[k][1]; // Stadt 1 + Stadt k
   }

   /** Berechne die überigen Mächtigkeitszahlen in C **/
   for(int s=3; s <= iN; s++)                 // Mächtigkeitszahl erhöhen, ohne 0,1,2
   {
      for(int S=(1<<(s-2)); S < (1<<iN); S++) // Beginne bei 2^(s-2), ende bei 2^iN
         if(NumberOfSetBits(S) == s)          // Menge mit der Mächtigkeitszahl s
            for(int k=2; k <= iN; k++)        // Alle Städte durchgehen
               if((S&(1<<(k-1))) > 0)         // Wenn Stadt k in Menge S vorkommt... && S >= (1<<(k-1))
               {
                  C[k][S] = INF;
                  for(int m=2; m <= iN; m++)  // Zweite Verbindungsstadt finden
                  {
                     if(m == k || (S&(1<<(m-1))) == 0) // m darf nicht gleich k sein & m muss in der Menge S vorhanden sein
                        continue;
                     C[k][S] = min(C[m][S^(1<<(k-1))]+d[m][k], C[k][S]); // Was ist kleiner der "neue" Wert oder der Ursprungswert?
                  }
               }
   }

   /** Optimum berechnen **/
   int opt = INF;
   for(int k=2; k <= iN; k++)
   {
      opt = min(C[k][(1<<(iN))-1]+d[1][k], opt);
   }

   printf("%i\n",opt);
   
   /*// Auskommentieren um die Optimums-Matrix auszugeben
   for(int i=2; i <= iN; i++)
   {
      for(int j=3; j < (1<<iN); j++)
      {
         printf("%i ",(C[i][j]<0?0:C[i][j]));
      }
      printf("\n\n");
   }*/

   // Pausieren
   //system("pause");

   return 0;
}

/** Bit-Zähler nach dem 'parallel'-Algorithmus (oder 'variable-precision SWAR'-Algorithmus) **/
int NumberOfSetBits(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

9999999