INF = 1 << 29
def solve
  memo = [INF] * (1<<$n)
  memo[0] = 0
  (1<<$n).times do |bits|
    next if memo[bits] == INF
    $n.times do |i|
      next if bits | (1<<i) == bits
      nbits = bits | (1<<i)
      mint = 0
      (0..$n).each do |j|
        k = $stg[i][j][0]
        if k == 0 || bits | 1<<(k-1) == bits
          mint = memo[bits] + $stg[i][j][1]
          break
        end
      end
      memo[nbits] = mint if memo[nbits] > mint
    end
  end
  memo[(1<<$n)-1]
end

while $n = gets.to_i
  break if $n == 0
  $stg = $n.times.map{ gets.split.map(&:to_i) }
  $stg.map! do |s|
    h = {}
    s.each_with_index{ |t, i| h[i] = t }
    h.sort_by{|k, v| v}
  end
  p solve
end