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
  result = []
  stack = [[0, 1, 0, 0, 0]]
  while (nxt = stack.shift)
    if nxt[1] == 2 ** n - 1
      result << nxt[2]
    else
      cpd[nxt[0]]
      .map {|path| [path, (table[path][0, 2] - [nxt[0]]).first, table[path].last]}
      .each do |path, spot, n|
        next if (nxt[4] & 2 ** path).nonzero?
        next if (2 ** spot & nxt[1]).nonzero? and (2 ** path & nxt[3]).zero?
        nxt_lnt = nxt[2]
        nxt_lnt += n if (2 ** spot & nxt[1]).zero?
        f = nxt[4]
        f |= 2 ** path if (2 ** path & nxt[3]).nonzero?
        stack << [spot, 2 ** spot | nxt[1], nxt_lnt, 2 ** path | nxt[3], f]
      end
    end
  end
  puts result.min
end
