#include using namespace std; vector dijkstra(vector>> &Graph,int start){ int N = Graph.size(); //O((V+E)logV) 一般最短経路魔法. long long inf = 3e18; vector used(N); vector ret(N,inf); priority_queue,vector>,greater>> Q; ret.at(start) = 0; Q.push({0,start}); while(Q.size()){ auto[nowd,pos] = Q.top(); Q.pop(); if(used.at(pos)) continue; used.at(pos) = true; for(auto [to,w] : Graph.at(pos)){ if(ret.at(to) > nowd+w){ ret.at(to) = nowd+w; Q.push({ret.at(to),to}); } } } return ret; } vector dijkstra2(vector>> &Graph,int start){ int N = Graph.size(); //O(V^2) 密グラフ専用. long long inf = 3e18; vector used(N); vector ret(N,inf); ret.at(start) = 0; while(true){ long long nowd = inf,pos = -1; for(int i=0; i ret.at(i)) nowd = ret.at(i),pos = i; } if(pos == -1) break; used.at(pos) = true; for(auto [to,w] : Graph.at(pos)){if(ret.at(to) > nowd+w) ret.at(to) = nowd+w;} } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); long long N,M,L,S,E; cin >> N >> M >> L >> S >> E; vector>> Graph(N+1); for(int i=0; i> u >> v; u--; v--; int w; cin >> w; Graph.at(u).push_back({v,w}); Graph.at(v).push_back({u,w}); } vector T(L); for(auto &t : T) cin >> t,t--; auto dist = dijkstra(Graph,0); if(dist.at(N-1) < S+E){cout << max(S+1,dist.at(N-1)+1) << "\n"; return 0;} for(auto &t : T){ if(dist.at(t) >= S+E) continue; Graph.at(N).push_back({t,max(S+1,dist.at(t)+1)}); } auto dist2 = dijkstra(Graph,N); if(dist2.at(N-1) >= 1e18) cout << -1 << "\n"; else cout << dist2.at(N-1) << "\n"; }