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 each_layer_from(start)
		reached = Set[start]
		current_layer = [start]
		loop {
			yield current_layer
			next_layer = []
			current_layer.each{|u|
				u.to_nodes.each{|v|
					next if reached.include?(v)
					reached << v
					next_layer << v
				}
			}	
			break if next_layer.empty?
			current_layer = next_layer
		}
	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)
}


f_dist = (1..n).map{ Float::INFINITY }
f_dist[0] = 0
f_unreached = (0..n-1).to_a
b_dist = (1..n).map{ Float::INFINITY }
b_dist[n-1] = 0
b_unreached = (0..n-1).to_a

f_min = b_min = 0
best = Float::INFINITY

loop.with_index {|_, itr|
	i = f_unreached.min_by{|i| f_dist[i]}
	break if i == n-1
	f_unreached.delete(i)
	u = orig_nodes[i]
	_, c, r = u.label
	f_min = f_dist[i]

	depth = 0	
	each_layer_from(u){|layer|
		layer.each{|v|
			j, _, _ = v.label
			d = f_dist[i] + c
			f_dist[j] = d if d < f_dist[j]
			best = d + b_dist[j] if d + b_dist[j] < best
		}
		break if depth == r
		depth += 1
	}

	i = b_unreached.min_by{|i| b_dist[i]}
	b_unreached.delete(i)
	b_min = b_dist[i]
	u = orig_nodes[i]
	depth = 0
	each_layer_from(u){|layer|
		layer.each{|v|
			j, c, r = v.label
			if depth <= r
				d = b_dist[i] + c
				b_dist[j] = d if d < b_dist[j]
				best = d + f_dist[j] if d + f_dist[j] < best
			end
		}
		depth += 1
	}
	break if f_min + b_min >= best

}
p best