require "set"
class Graph
  def initialize
    @nodes = Set.new
    @edges = {}
  end

  def add_edge! node1, weight, node2
    @nodes << node1
    @nodes << node2
    @edges[node1] ||= Set.new
    @edges[node2] ||= Set.new
    @edges[node1] << [weight, node2]
  end

  def minimum_weight s_node, e_node
    # 最短経路問題を解く
    remain = @nodes.clone
    dist = {s_node => 0}
    prev = {}
    while not remain.empty?
      node = remain.to_a.min{|n1, n2| (dist[n1] || Float::INFINITY) <=>(dist[n2] || Float::INFINITY)}
      remain.delete node
      @edges[node].each do |value|
        weight, node1 = value
        if (dist[node1] || Float::INFINITY) > ((dist[node] || Float::INFINITY) + weight) then
          dist[node1] = (dist[node] || Float::INFINITY) + weight
          prev[node1] = node
        end
      end
    end
    return dist[e_node] || Float::INFINITY
  end
end

def main
  n, m, x = gets.chomp.split(" ").map(&:to_i)
  graph = Graph.new
  height = {}
  n.times do |i|
    i = i+1
    h = gets.to_i
    height[i] = h
    h.times do |h|
      graph.add_edge! [i, h], 1, [i, h+1]
      graph.add_edge! [i, h+1], 1, [i, h]
    end
  end
  m.times do |j|
    i1, i2, t = gets.chomp.split(" ").map(&:to_i)
    (t..height[i1]).each do |k|
      graph.add_edge! [i1, k], t, [i2, k-t]
    end
    (t..height[i2]).each do |k|
      graph.add_edge! [i2, k], t, [i1, k-t]
    end
  end
  result = graph.minimum_weight [1,x],[n,height[n]]
  return result == Float::INFINITY ? -1 : result
end

puts main