require 'set'
loop do
    n = gets.to_i
    break if n == 0
    t = n.times.map{gets.split.map(&:to_i)}
    m = Array.new(n+1).map{Hash.new(Float::INFINITY)}
    1.upto(n) do |i|
        m[i][Set.new] = t[i-1][0]
    end
    n.times do 
        1.upto(n) do |i|
            1.upto(n) do |j|
                next if i == j
                h = m[i].dup
                m[j].each do |k,v|
                    next if k.include?(i)
                    kk = Marshal.load(Marshal.dump(k))
                    nk = kk.add(j)
                    min = nk.map{|l| t[i-1][l]}.min
                    h[nk] = v + min
                end
                m[i] = h
            end
        end
    end
    p m[1...m.size].map{|a| a.select{|k,v| k.size == n - 1}.map{|k,v| v}.min}.min
end