until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  field = [[0, 0]]
  Array.new(m) {$<.gets.split(",").map(&:to_i)}.each do |a, b, d|
    n = d / 100 - 1
    field += field.map do |spots, num|
      spots |= 2 ** a
      spots |= 2 ** b
      [spots, num + n]
    end
  end
  puts field.select {|x| x.first == 2 ** n - 1}.sort_by {|x| x.last}.first.last
end
