#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <bit>
using i64 = long long;
/*
Tree rooted at E
escaping just ancestor problem: have range in dfs traversal for start and stop, check containment
every node stores how far to store downwards (or LARGE_NUM if none)
if not ancestor, escapes. Else: find closest store, but in subtree under cut
can using RMQ (using sparse table) for LCA do it in O(amount of stores in subtree) per node
*/
#include <stdint.h>
static inline uint32_t log2(const uint32_t x) {
uint32_t y;
asm ( "\tbsr %1, %0\n"
: "=r"(y)
: "r" (x)
);
return y;
}
constexpr i64 LARGE = 1ll<<60;
struct Node;
struct Road
{
int a,b;
i64 W;
};
std::vector<Node> nodes;
std::vector<Road> roads;
struct NodeP
{
int num;
Node& operator*() const;
Node* operator->() const;
NodeP(int num=0) : num(num) {}
NodeP(Node*p);
operator int() const {return num;}
};
struct Node
{
std::set<std::pair<NodeP,i64>> c;
NodeP p;
i64 p_d;
i64 dist_store_down=LARGE; // 0 <=> this is a store
int first,last; // when doing traversal, first and last place of this node
int height;
Node() {}
};
std::vector<NodeP> traversal;
NodeP::NodeP(Node* p) : num(p-&nodes[0]) {}
Node& NodeP::operator*() const {return nodes[num];}
Node* NodeP::operator->() const {return &nodes[num];}
void traverse(NodeP n)
{
traversal.push_back(n);
n->first = traversal.size();
for(auto[c,d] : n->c)
{
c->c.erase({n,d});
c->p = n;
c->p_d = d;
c->height = n->height+1;
traverse(c);
n->dist_store_down = std::min(n->dist_store_down,c->dist_store_down+d);
traversal.push_back(n);
}
n->last = traversal.size();
}
//template<typename T,T comb(T,T)>
struct sparsetable
{
using T = NodeP;
std::vector<std::vector<T>> data;
static T comb(T a,T b)
{
return a->height < b->height ? a : b;
}
sparsetable() {}
sparsetable(std::vector<T> d)
{
auto N = d.size();
data.push_back(std::move(d));
for(int s = 1; s < N; s<<=1)
{
auto& v = data.emplace_back();
const auto& p = data[data.size()-2];
for(int i = 0; i + s < p.size(); i++)
{
v.push_back(comb(p[i],p[i+s]));
}
}
}
T query(int l, int r)
{
unsigned int d = r-l;
auto s = log2(d);
return comb(data[s][l],data[s][r-(1<<s)]);
}
} sp;
NodeP LCA(NodeP a, NodeP b)
{
if(a->first > b->first) std::swap(a,b);
return sp.query(a->first,b->first);
}
bool parent(NodeP a,NodeP b) // b parent of a
{
return b->first <= a->first && a->first <= b->last;
}
int main()
{
int N,S,Q,E;
std::cin >> N >> S >> Q >> E;
nodes.resize(N+1);
roads.resize(N);
for(auto& i : roads)
{
if(&i==&roads[0]) continue;
std::cin >> i.a >> i.b >> i.W;
nodes[i.a].c.emplace(&nodes[i.b],i.W);
nodes[i.b].c.emplace(&nodes[i.a],i.W);
}
for(int i = 0; i < S; i++)
{
int C;
std::cin >> C;
nodes[C].dist_store_down = 0;
}
NodeP e = &nodes[E];
traverse(e);
sp = decltype(sp)(std::move(traversal));
std::vector<i64> result; result.reserve(Q); // -1 - escaped; -2 - oo
for(int i = 0; i < Q; i++)
{
int I,_R;
std::cin >> I >> _R;
auto _cut = roads[I];
NodeP cut = nodes[_cut.a].height < nodes[_cut.b].height ? &nodes[_cut.b] : &nodes[_cut.a]; // highest height
NodeP R = &nodes[_R];
if(!parent(R,cut)) {result.push_back(-1);continue;}
if(R->dist_store_down==0) {result.push_back(0); continue;}
if(cut->dist_store_down>=LARGE) {result.push_back(-2);continue;}
i64 d = 0;
i64 mind = R->dist_store_down;
auto p = R;
do
{
d+=p->p_d;
p=p->p;
mind = std::min(mind,p->dist_store_down+d);
} while (p != cut);
result.push_back(mind);
}
for(auto i : result)
{
if(i==-2) std::cout << "oo\n";
else if (i==-1) std::cout << "escaped\n";
else std::cout << i << "\n";
}
}
