INF = 1 << 29
def dfs(bits)
  return if $memo[bits] == INF
  $n.times do |i|
    if bits | (1<<i) != bits
      nbits = bits | (1<<i)
      (0..$n).each do |j|
        sn = $stg[i][j][0]
        if sn == 0 || bits & (1<<(sn-1)) == 1<<(sn-1)
          t = $memo[bits] + $stg[i][j][1]
          if $memo[nbits] > t
            $memo[nbits] = t
            dfs(nbits)
          end
        end
      end
    end
  end
end

while $n = gets.to_i
  break if $n == 0
  $memo = [INF] * (1<<$n)
  $memo[0] = 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
  dfs(0)
  p $memo[(1<<$n)-1]
end