
object Main extends App {

  import scala.io.StdIn._
  import scala.math._
  solve
  def solve: Unit = {
    val n = readLine.trim.toInt
    if (n == 0) return
    val hates = Array.tabulate(n) { _ ⇒ readLine.trim.split(' ').map(_.toInt) }
    for {i ← 0 until n
         j ← 0 until n}{
      hates(i)(j) = math.max(hates(i)(j), hates(j)(i))
      hates(j)(i) = hates(i)(j)
    }
    println(
      (for (order ← (0 until n).permutations) yield {
      var position: List[(Int, Int)] = List((order.head, 0))
      for (n ← order.tail){
        position ::= (n, position.map{case (h, d) ⇒ d + hates(n)(h)}.max)
      }
      position.head._2
    }).min
    )
    solve
  }
  implicit class Extension[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}
