module Graph
	require 'set'
	def add_node(label = nil)
		Node.new(label)
	end

	def add_edge(u, v, label = nil)
		e = Edge.new(u, v, label)
		u.outgoings << e
		v.incomings << e
		e
	end

	def del_edge(e)
		u, v = e.from, e.to
		u.outgoings.delete(e)
		v.incomings.delete(e)
		e
	end
	
	class Node
		def initialize(label)
			@label = label
			@outgoings = Set.new
			@incomings = Set.new
		end

		def to_nodes
			@outgoings.map(&:to)
		end

		def from_nodes
			@incomings.map(&:from)
		end


		def to_s
			@label
		end
		
		attr_accessor :outgoings, :incomings
		attr_reader :label
	end

	class Edge
		def initialize(u, v, label = nil)
			@from = u	
			@to = v
			@label = label
		end
		attr_reader :from, :to, :label
	end

	def until_depth(d, start)
		reached = Set[start]
		current_layer = [start]
		
		loop {
			next_layer = []
			current_layer.each{|u|
				u.to_nodes.each{|v|
					next if reached.include?(v)
					reached << v
					next_layer << v
				}
			}	
			d -= 1
			break if d == 0 || next_layer.empty?
			current_layer = next_layer
		}

		reached.to_a
	end
end

extend Graph

n, k = gets.split.map &:to_i
orig_nodes = (0..n-1).map{|i|
	add_node([i] + gets.split.map(&:to_i)) 
}

k.times {
	i, j = gets.split.map &:to_i
	u = orig_nodes[i-1]
	v = orig_nodes[j-1]
	add_edge(u, v)
	add_edge(v, u)
}


dist = (1..n).map{ Float::INFINITY }
dist[0] = 0
unreached = (0..n-1).to_a

loop.with_index {|_, itr|
	i = unreached.min_by{|i| dist[i]}
	#p [itr, i]
	break if i == n-1
	unreached.delete(i)
	u = orig_nodes[i]
	_, c, r = u.label
	until_depth(r, u).each{|v|
		j, _, _ = v.label
		d = dist[i] + c
		dist[j] = d if d < dist[j]
	}
}
p dist[n-1]