until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  cpd = Hash.new([])
  table = Array.new(m) {$<.gets.split(",").map(&:to_i)}
  table.map! {|a, b, d| [a, b, d / 100 - 1]}
  table.each_with_index do |x, i|
    cpd[x[0]] += [i]
    cpd[x[1]] += [i]
  end
  stack = [[0, 1, 0, 0]]    # 現在位置、行った場所、灯籠の数、使った道
  result = loop do
    nxt = stack.shift
    cpd[nxt[0]]
    .map {|tn| [tn, (table[tn][0, 2] - [nxt[0]]).first, table[tn].last]}
    .each do |tn, spot, n|
      nxt_lnt = nxt[2]
      nxt_lnt += n if (2 ** spot & nxt[1]).zero?
      stack << [spot, 2 ** spot | nxt[1], nxt_lnt, 2 ** tn | nxt[3]]
    end
    tmp1 = stack.select {|x| x[1] == 2 ** n - 1}
    tmp2 = tmp1 .select {|x| x[3] == 2 ** m - 1}
    break tmp1 unless tmp2.empty?
  end
  puts result.map {|x| x[2]}.min
end
