### constant

MAX_INT = 1 << 30

### subroutines

def d_rec(k)
  if k >= $n
    d = $ds.last
    $min_d = d if $min_d > d
    return
  end

  for i in (0...$n)
    next if $used[i]

    d0 = (k == 0) ? 0 : (0...k).map{|j| $ds[j] + $mat[$hs[j]][i]}.max
    if d0 < $min_d
      $used[i] = true
      $ds[k] = d0
      $hs[k] = i
      d_rec(k + 1)
      $used[i] = false
    end
  end
end

### main

loop do
  $n = gets.to_i
  break if $n == 0

  $mat = []
  $n.times do
    yline = gets.split.map(&:to_i)
    $mat << yline
  end
  #p $mat

  for i in (0...$n)
    for j in ((i + 1)...$n)
      m = [$mat[i][j], $mat[j][i]].max
      $mat[i][j] = $mat[j][i] = m
    end
  end
  #p $mat

  $used = $n.times.map{false}
  $ds = []
  $hs = []

  $min_d = MAX_INT
  d_rec(0)

  puts $min_d
end