class BinaryHeap def initialize @data = Array(Int64).new end def size @data.size end def empty? @data.size == 0 end def insert(x) idx = @data.size @data << x while idx > 0 && priority(@data[idx], @data[(idx - 1) >> 1]) @data[(idx - 1) >> 1], @data[idx] = @data[idx], @data[(idx - 1) >> 1] idx = (idx - 1) >> 1 end end def << (x) insert(x) end def pop return nil if @data.size == 0 return @data.pop if @data.size == 1 r = @data[0].dup @data[0] = @data.pop idx = 0 while (n_idx = 2 * idx + 1) < @data.size n_idx += 1 if n_idx + 1 < @data.size && priority(@data[n_idx + 1], @data[n_idx]) break if priority(@data[idx], @data[n_idx]) @data[idx], @data[n_idx] = @data[n_idx], @data[idx] idx = n_idx end r end def top self.empty? ? nil : @data[0] end def priority(a, b) # return true iff a has higher priority than b (a >> 30) < (b >> 30) end end INF = 1 << 30 Mask = (1 << 30) - 1 n, m, l, s, e = read_line.split.map &.to_i g = Array.new(n << 1) {[] of Array(Int32)} m.times do a, b, t = read_line.split.map &.to_i a -= 1 b -= 1 2.times do g[a] << [b, t] g[b] << [a, t] a += n b += n end end t = Array.new(n, false) read_line.split.map(&.to_i).each do |i| t[i - 1] = true end q = BinaryHeap.new q << 0_i64 dist = Array.new(n << 1, INF) dist[0] = 0 while (ud = q.pop) u, d = ud & Mask, ud >> 30 next if dist[u] < d g[u].each do |(v, c)| next if dist[v] <= dist[u] + c dist[v] = dist[u] + c q << (dist[v].to_i64 << 30 | v) end if u < n && t[u] && dist[u] < s + e && dist[u + n] > [dist[u] + 1, s + 1].max dist[u + n] = [dist[u] + 1, s + 1].max q << (dist[u + n].to_i64 << 30 | (u + n)) end end puts dist[-1] == INF ? -1 : dist[-1]