object Main extends App {
  import scala.io.StdIn._

  val prevs = Array.tabulate(10){_ ⇒ 0}
  val position = Array.tabulate(10){_ ⇒ 0}
  solve
  def solve: Unit = {
    val n = readInt
    if (n == 0) return
    val nodes = Array.tabulate(n){_ ⇒ readLine.trim.split(' ').map(_.toInt)}
    for (i ← 0 until n; j ← 0 until n if i != j) nodes(i)(j) = math.max(nodes(i)(j), nodes(j)(i))
    var min = Int.MaxValue
    sub(n - 1, 0)
    println(min)
    solve
    def sub(next: Int, flag: Int): Unit= {
      if (next < 0) {
        if (position.head < min)
          min = position.head
      }else{
        for (i ← 0 until n if ((1 << i) & flag) == 0){
          prevs(next) = i
          position(next) = 0
          for (j ← next + 1 until n) {
            if (position(next) < nodes(prevs(j))(i) + position(j)) {
              position(next) = nodes(prevs(j))(i) + position(j)
            }
          }
          if (position(next) < min) sub(next - 1, flag | (1 << i))
        }
      }
    }
  }
}

