### constant

INF = 1 << 30

### main

loop do
  n, m = gets.split.map(&:to_i)
  break if (n | m) == 0

  st = 0
  gl = n - 1
  gbit = 1 << gl
  
  ds = []
  ds[st] = ds[gl] = 0
  es = []
  es[st] = 0
  es[gl] = 1000

  for i in ((st + 1)...gl)
    ds[i], es[i] = gets.split.map(&:to_i)
  end
  #p [ds, es]

  edges = Array.new(n){Array.new(n){nil}}
  nbrs = Array.new(n){[]}
  
  m.times do
    ai, bi, ci = gets.split.map(&:to_i)
    ai -= 1
    bi -= 1
    edges[ai][bi] = ci
    nbrs[ai] << bi
  end
  #p edges
  #p nbrs

  costs = Array.new(n){Hash.new(INF)}
  costs[st][0] = 0

  q = [[st, 0]]
  min_c = INF
  
  while ! q.empty?
    u = q.min{|a, b| costs[a[0]][a[1]] <=> costs[b[0]][b[1]]}
    q.delete(u)

    ui, ubits = u
    ue = es[ui]
    uc = costs[ui][ubits]
    go = ((ubits & gbit) == 0)

    if ui == st && ! go
      min_c = uc if min_c > uc
      next
    end
    
    for vi in nbrs[ui]
      if go && es[ui] <= es[vi] || ! go && es[ui] >= es[vi]
        vbit = 1 << vi
        vc = uc + edges[ui][vi]
        vc += ds[vi] if (ubits & vbit) == 0
        vbits = ubits | vbit

        if costs[vi][vbits] > vc
          costs[vi][vbits] = vc
          q << [vi, vbits]
        end
      end
    end
  end

  puts (min_c >= INF ? -1 : min_c)
end