n, m = gets.split.map(&:to_i)
keys = m.times.map { [gets.split.map(&:to_i), gets.split.map(&:to_i)] }

ans = m.times.map do |i|
  k = keys.map {|(a, b), c| [a, c] }.combination(i + 1).map {|x| x }
  costs = k.map { |j| j.reduce(0) { |s, cn| s + cn[0] }}
  boxes = k.map { |j| j.map { |(a, b)| b }.flatten }.map(&:uniq)
  costs.zip(boxes).reject {|(c, a)| a.size < n }.min { |(c1, a1), (c2, a2)| c1 <=> c2 }
end.compact.min { |(c1, a1), (c2, a2)| c1 <=> c2 }

p ans.nil? ? -1 : ans[0]