loop {
	n = gets.to_i
	break if n == 0
	a = (1..n).map{ gets.split.map &:to_i }
	
	table = Array.new(1<<n, Float::INFINITY)
	table[0] = 0
	for x in 1..(1<<n)-1
		idx = (0..n-1).select{|i| x[i] == 1}
		min_time = Float::INFINITY
		for i in idx
			prev_t = table[x-(1<<i)]
			cost_table = a[i]
			min_cost = cost_table[0]
			for j in idx - [i]
				c = cost_table[j+1]
				min_cost = c if c < min_cost
			end
			t = prev_t + min_cost
			min_time = t if t < min_time
		end
		table[x] = min_time
	end
	p table[-1]
}