import sys import itertools import time import heapq from math import radians, sin, cos, tan, sqrt, comb, pow from math import log, log2, log10, exp from collections import deque from operator import mul from functools import reduce, cmp_to_key from random import randint, randrange from bisect import bisect_left, bisect_right def input(): return sys.stdin.readline().replace('\n','') #sys.setrecursionlimit(300000) md1 = 998244353 md2 = 10 ** 9 + 7 inf = 2 ** 31 + 1 primeset = set() primelist = [] fenwick = [] # 入力ツール # 1行の入力を整数のリストとして受け取る def intlist(): return list(map(int, input().split())) # 1行から複数個の整数を受け取る def getints(): return tuple(map(int, input().split())) # n行の入力を文字列のリストとして受け取る def strtable(n): lst = [] for i in range(0, n): lst.append(input()) return lst # n行の入力を整数のリストとして受け取る def inttable(n): return list(map(int, strtable(n))) # 整数のリストをn個受け取る def intlisttable(n): lst = [] for i in range(0, n): lst.append(intlist()) return lst # n個のクエリを先頭だけ整数、他を文字列のリストとして受け取る def getquery(n): lst = [] for i in range(0, n): query = list(input().split()) qr = int(query[0]) lst.append((qr, query[1:])) return lst #========== # 生成ツール # H行W列のリスト生成 def twodimlist(h, w, init): # initの値で初期化 lst1 = [] for i in range(0, h): lst2 = [] for j in range(0, w): lst2.append(init) lst1.append(lst2) return lst1 # 素数テーブルをsetとして生成 def genprimeset(n): #n以下の素数を列挙 global primeset, primelist left = list(primeset) right = deque() start = 2 if len(left) != 0: start = pt[-1] + 1 for i in range(start, n+1): right.append(i) while len(right) != 0: flag = True now = right.popleft() for i in range(0, len(left)): if now < left[i] ** 2: break if now % left[i] == 0: flag = False break if flag: left.append(now) return set(left) #========== # 数え上げ # 1次元数え上げ def cntx(itr, x): cnt = 0 for i in range(0, len(itr)): if itr[i] == x: cnt += 1 return cnt # 2次元数え上げ def twodimcntx(itr, x): sm = 0 for i in range(0, len(itr)): sm += cntx(itr[i], x) return sm # 全要素数え上げ def allcnt(itr): dct = {} for i in range(0, len(itr)): if itr[i] not in dct: dct[itr[i]] = 0 dct[itr[i]] += 1 return dct # 2次元全要素数え上げ def twodimallcnt(itr, x): dct = {} for i in range(0, len(itr)): for j in range(0, len(itr[i])): if itr[i][j] not in dct: dct[itr[i][j]] = 0 dct[itr[i][j]] += 1 return dct #========== # 計算ツール # 最大公約数 def gcd(x, y): if x < y: return gcd(y, x) if x % y == 0: return y return gcd(y, x%y) # 最小公倍数 def lcm(x, y): g = gcd(x, y) return (x*y) // g # フィボナッチ数列(0-indexで、第n項まで生成) def genfib(n, m): # m == 0ならmodなし、m == 1ならmd1でmod, m == 2ならmd2でmod lst = [1, 1] if m == 0: for i in range(1, n): lst.append(lst[-2]+lst[-1]) else: md = md1 if m == 2: md = md2 for i in range(1, n): lst.append((lst[-2]+lst[-1])%md) return lst # 素数一覧の初期化 def primeinit(x): global primeset, primelist primeset = genprimeset(x) primelist = list(primeset) return # 素数判定 def isitprime(x): if x < 2: return False global primeset, primelist if len(primeset) == 0: primeinit(int(sqrt(x))+10) elif primelist[-1] ** 2 < x: primeinit(int(sqrt(x))+10) if x in primeset: return True for i in range(0, len(primelist)): if x % primelist[i] == 0: return False return True # 素因数分解 def factorize(x): global primeset, primelist if len(primeset) == 0: primeinit(int(sqrt(x))+10) elif primelist[-1] ** 2 < x: primeinit(int(sqrt(x))+10) dct = {} now = x for i in range(0, len(primelist)): if x < primelist[i] ** 2: break while now % primelist[i] == 0: if primelist[i] not in dct: dct[primelist[i]] = 0 dct[primelist[i]] += 1 now //= primelist[i] if now != 1: dct[now] = 1 return dct # Coprime判定 def coprime(x, y): return gcd(x, y) == 1 # 約数列挙 def divisor(x): s = set() for i in range(1, x+1): if x < i ** 2: break if x % i == 0: s.add(i) s.add(x//i) lst = sorted(list(s)) return lst # 約数数え上げ def countdivisor(x): fact = factorize(x) key = list(fact.keys()) cnt = 1 for i in range(0, len(key)): cnt *= fact[key[i]] + 1 return cnt # 大文字->小文字変換 def uppertolower(c): if 'A' <= c and c <= 'Z': return chr(ord(c)+32) return c # 小文字->大文字変換 def lowertoupper(c): if 'a' <= c and c <= 'z': return chr(ord(c)-32) return c # 大文字小文字相互変換 def upperlower(c): newc = uppertolower(c) if c == newc: newc = lowertoupper(c) return newc # x以上の要素の個数 def xormore(lst, x): # lstはソート済みにすること return len(lst) - bisect_left(lst, x) # xより大きい要素の個数 def morethanx(lst, x): # lstはソート済みにすること return len(lst) - bisect_right(lst, x) # x以下の要素の個数 def xorless(lst, x): # lstはソート済みにすること return bisect_right(lst, x) # x未満の要素の個数 def lessthanx(lst, x): # lstはソート済みにすること return bisect_left(lst, x) # 各桁の総和 def digitsum(x): nm = str(x) sm = 0 for i in range(0, len(nm)): sm += int(nm[i]) return sm # bitカウント(64bitまで) def popcount(x): now = x now = now - ((now >> 1) & 0x5555555555555555) now = (now & 0x3333333333333333) + ((now >> 2) & 0x3333333333333333) now = (now + (now >> 4)) & 0x0f0f0f0f0f0f0f0f n = 8 for i in range(0, 3): now += (now >> n) n *= 2 return now & 0x0000007f # xの累乗リスト(0乗からn乗まで) def powtable(x, n, m): # modなしの場合はm = 0に設定する md = m if m == 1: # m == 1ならmd1でmod md = md1 elif m == 2: # m == 2ならmd2でmod md = md2 lst = [1] for i in range(0, n): if md == 0: lst.append(lst[-1]*x) else: lst.append((lst[-1]*x)%md) return lst # ========== # グラフツール # グラフの初期化 def defgraph(vlist): graph = {} for i in range(0, len(vlist)): graph[vlist[i]] = set() return graph # 重み付きグラフの初期化 def defgraphw(vlist): graph = {} for i in range(0, len(vlist)): graph[vlist[i]] = {} return graph # 無向グラフ生成 def undirgraph(vlist, elist): # 辺の形式は(u, v) graph = defgraph(vlist) for i in range(0, len(elist)): u = elist[i][0] v = elist[i][1] graph[u].add(v) graph[v].add(u) return graph # 重み付き無向グラフ生成 def undirgraphw(vlist, elist, wdict): graph = defgraphw(vlist) for i in range(0, len(elist)): u = elist[i][0] v = elist[i][1] graph[u][v] = wdict[elist[i]] graph[v][u] = wdict[elist[i]] return graph # 有向グラフ生成 def dirgraph(vlist, elist): # 辺の形式は(u, v)で、向きはu -> v graph = defgraph(vlist) for i in range(0, len(elist)): u = elist[i][0] v = elist[i][1] graph[u].add(v) return graph # 重み付き有向グラフ生成 def dirgraphw(vlist, elist, wdict): graph = defgraphw(vlist) for i in range(0, len(elist)): u = elist[i][0] v = elist[i][1] graph[u][v] = wdict[elist[i]] return graph # 重み無し最短ステップ def shortest(vlist, elist, graph, st, gl): if st not in graph or gl not in graph: return -1 yet = set(vlist) q = deque() q.append((st, 0)) yet.discard(st) while len(q) != 0: now = q.popleft() v = now[0] s = now[1] if v == gl: return s lst = list(graph[v]) for i in range(0, len(lst)): nxtv = lst[i] if nxtv in yet: yet.discard(nxtv) q.append((nxtv, s+1)) return -1 # ダイクストラ def dijkstra(vlist, elist, graph, st): cur = {} for i in range(0, len(vlist)): cur[vlist[i]] = inf cur[st] = 0 dist = {} h = [] heapq.heapify(h) heapq.heappush(h, (0, st)) while len(h) != 0: now = heapq.heappop(h) d = now[0] v = now[1] if v in dist: continue dist[v] = d lst = list(graph[v].keys()) for i in range(0, len(lst)): nxt = lst[i] if nxt not in dist: nxtd = dist[v] + graph[v][nxt] cur[nxt] = min(cur[nxt], nxtd) if cur[nxt] == nxtd: heapq.heappush(h, (nxtd, nxt)) return dist # Union-Find生成 def genunionfind(vlist, elist): # 辺の形式は(u, v) graph = defgraph(vlist) root = {} vcnt = {} flag = False for i in range(0, len(vlist)): root[vlist[i]] = vlist[i] vcnt[vlist[i]] = 1 for i in range(0, len(elist)): u = elist[i][0] v = elist[i][1] ur = root[u] vr = root[v] if ur == vr: flag = True else: H = ur L = vr if vcnt[ur] < vcnt[vr]: H = vr L = ur graph[H].add(L) vcnt[H] += vcnt[L] q = deque() q.append(L) while len(q) != 0: now = q.popleft() root[now] = H lst = list(graph[now]) for j in range(0, len(lst)): q.append(lst[j]) return (graph, root, vcnt, flag) # (グラフ, 根, 頂点の数, ループ検出)の形式で返す # ========== # fenwick木 # fenwickを初期化 def initfenwick(n, init): global fenwick fenwick = [] for i in range(0, n+1): fenwick.append(init) return # idx番目までの和を求める def fwsum(idx): sm = 0 now = idx while now > 0: sm += fenwick[now] now -= -now & now return sm # idx番目の値にxを足す def fwadd(idx, x): global fenwick now = idx while now < len(fenwick): fenwick[now] += x now += -now & now return # 転倒数 def inversion(A): global fenwick initfenwick(len(A), 0) sm = 0 for i in range(0, len(A)): sm += i - fwsum(A[i]) fwadd(A[i], 1) return sm # ========== # ハッシュ Mset = set() Mlist = [] # Mの候補の素数を生成 def initM(): global Mset, Mlist a = 10 ** 9 for i in range(-10000, 10001): if isitprime(a+i): Mset.add(a+i) Mlist = list(Mset) return # Bの累乗を生成 def genB(b, m, n): lst = [1] for i in range(0, n): lst.append((lst[-1]*b)%m) return lst # ハッシュテーブル生成 def genH(b, m, s): lst = [0] for i in range(0, len(s)): a = ord(s[i]) - ord('a') + 1 lst.append((b*lst[-1]+a)%m) return lst # 部分文字列のハッシュ値を求める def Hval(Hlist, Blist, M, L, R): return (Hlist[R] - Blist[R-L+1]*Hlist[L-1]) % M # ハッシュを複数生成 def multihash(s): global Mset, Mlist if len(Mlist) == 0: initM() bm = {} for i in range(0, 5): b = randint(9900, 11000) m = Mlist[randrange(0, len(Mlist))] while (b, m) in bm: b = randint(9900, 11000) m = Mlist[randrange(0, len(Mlist))] Blist = genB(b, m, len(s)) Hlist = genH(b, m, s) bm[(b, m)] = (Blist, Hlist) return bm # 指定したb, mでハッシュ生成 def multihashconst(s, bmkey): h = {} for i in range(0, 5): b = bmkey[i][0] m = bmkey[i][1] Blist = genB(b, m, len(s)) Hlist = genH(b, m, s) h[(b, m)] = (Blist, Hlist) return h # ========== # 【問題要約】 # 地点がN個あり、それぞれに1からNまでの番号が振られている # 地点と地点をつなぐ道がM本あり、道i(where 1<=i<=M)は # 地点a_iとb_iを双方向に結んでいる # また、道iを通過するのにt_i分かかる # 自己ループや二重辺がある可能性がある # 現在地は地点1, 目的地は地点Nである # 道を通って地点に移動することと、今いる地点に任意の時間だけ留まることを選択できる # S分後からE+0.1分間の間にトイレに寄る必要がある # トイレはL個あり、地点T_j(where 1<=j<=L)にある # ただし、T_L == N である # トイレで用をたすのには1分かかる # つまり、S分後からS+E-0.99分後の間にいずれかのトイレがある地点に到着し、 # そこに1分以上とどまる必要がある # 用を済ませた上で学校に辿り着くためにかかる時間の最小値を求めよ # トイレに間に合わない、もしくは目的地にたどりつけない場合は-1を出力せよ # # 2 <= N <= 200000 # 1 <= M <= 200000 # 1 <= L <= N # 1 <= S, E <= 10^9 # 1 <= a_i, b_i <= N # 1 <= t_i <= 10^9 # 1 <= T_1 < T_2 < ... < T_L == N # 入力はすべて整数 # # ========== # コードはここから書く N, M, L, S, E = getints() vlist = list(range(1, N+1)) eset = set() wdict = {} for i in range(0, M): a, b, t = getints() if a != b: e = (min(a, b), max(a, b)) eset.add(e) if e not in wdict: wdict[e] = inf wdict[e] = min(wdict[e], t) elist = list(eset) graph = undirgraphw(vlist, elist, wdict) T = set(intlist()) beforecur = {} aftercur = {} for i in range(0, len(vlist)): beforecur[vlist[i]] = inf aftercur[vlist[i]] = inf beforecur[1] = 0 beforedist = {} afterdist = {} h = [] heapq.heapify(h) heapq.heappush(h, (0, 1, False)) while len(h) != 0: now = heapq.heappop(h) d = now[0] v = now[1] toilet = now[2] if toilet: if v in afterdist: continue afterdist[v] = d else: if v in beforedist: continue beforedist[v] = d if v in T: if d <= S: heapq.heappush(h, (S+1, v, True)) elif d < S + E: heapq.heappush(h, (d+1, v, True)) lst = list(graph[v]) for i in range(0, len(lst)): nxt = lst[i] if toilet: if nxt not in afterdist: nxtd = afterdist[v] + graph[v][nxt] aftercur[nxt] = min(aftercur[nxt], nxtd) if aftercur[nxt] == nxtd: heapq.heappush(h, (nxtd, nxt, toilet)) else: if nxt not in beforedist: nxtd = beforedist[v] + graph[v][nxt] if nxtd < S + E: beforecur[nxt] = min(beforecur[nxt], nxtd) if beforecur[nxt] == nxtd: heapq.heappush(h, (nxtd, nxt, toilet)) if N in afterdist: print(afterdist[N]) else: print(-1)