## constant

MAX_INT = 1 << 31

### subroutines

def is_valid?(dists, i, r, d)
  dihash = dists[i]
  for r0 in dihash.keys
    if r0 >= r && dihash[r0] <= d
      return false
    end
  end
  true
end

### main

n, k = gets.strip.split(' ').map{|s| s.to_i}

taxis = n.times.map{gets.strip.split(' ').map{|s| s.to_i}}
#p taxis

nbrs = n.times.map{[]}

k.times do
  ai, bi = gets.strip.split(' ').map{|s| s.to_i - 1}
  nbrs[ai] << bi
  nbrs[bi] << ai
end
#p nbrs

dists = n.times.map{Hash.new(MAX_INT)}
dists[0][0] = 0
q = [[0, 0]]

while ! q.empty?
  u = q.min{|a, b| dists[a[0]][a[1]] <=> dists[b[0]][b[1]]}
  q.delete u

  ui, ur = u
  next if ui == n - 1

  du = dists[ui][ur]

  if ur > 0
    vr = ur - 1
    for vi in nbrs[ui]
      if is_valid?(dists, vi, vr, du)
        dists[vi][vr] = du
        q << [vi, vr]
      end
    end
  end

  cu, ur = taxis[ui]
  dv = du + cu
  vr = ur - 1

  for vi in nbrs[ui]
    if is_valid?(dists, vi, vr, dv)
      dists[vi][vr] = dv
      q << [vi, vr]
    end
  end
end
#p dists

puts dists[n - 1].values.min