#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;}
//operator bool() const {return num;}
};
NodeP mincombD(NodeP a, NodeP b);
template<NodeP comb(NodeP,NodeP)>
struct sparsetable;
struct Node
{
std::set<std::pair<NodeP,i64>> c;
NodeP p;
i64 p_d;
i64 dist_store_down=LARGE; // 0 <=> this is a store
i64 dist_up;
int first,last; // when doing traversal, first and last place of this node
int height;
int size;
std::vector<std::pair<NodeP,NodeP>> par; //(grand)parent, mincombD
int heavy_idx;
sparsetable<mincombD>* heavy;
NodeP heavyc;
Node() {}
};
std::ostream& operator<<(std::ostream& os,const NodeP p)
{
os << p.num << " ";
if(p->heavyc) os << "(" << p->heavyc << " ";
for(auto[c,d] : p->c) if(c!=p->heavyc) os << c << " ";
if(p->heavyc) os << ")";
return os;
}
std::vector<NodeP> traversal;
NodeP::NodeP(Node* p) : num(p-&nodes[0]) {}
Node& NodeP::operator*() const {return num ? nodes[num] : *(Node*)nullptr;}
Node* NodeP::operator->() const {return num ? &nodes[num] : nullptr;}
void traverse(NodeP n)
{
traversal.push_back(n);
n->first = traversal.size();
n->size = 1;
if(n->p)
{
n->par.emplace_back(n->p,mincombD(n,n->p));
while(n->par.back().first->par.size()>=n->par.size())
{
n->par.emplace_back(n->par.back().first->par[n->par.size()-1].first,
mincombD(n->par.back().second,n->par.back().first->par[n->par.size()-1].second));
}
}
NodeP maxc;
for(auto[c,d] : n->c)
{
c->c.erase({n,d});
c->p = n;
c->p_d = d;
c->height = n->height+1;
c->dist_up = n->dist_up + d;
traverse(c);
n->size += c->size;
if(!maxc || c->size > maxc->size) maxc=c;
n->dist_store_down = std::min(n->dist_store_down,c->dist_store_down+d);
traversal.push_back(n);
}
n->heavyc = maxc;
n->last = traversal.size();
}
//template<typename T,T comb(T,T)>
NodeP lowHeight(NodeP a, NodeP b)
{
return a->height < b->height ? a : b;
}
NodeP mincombD(NodeP a, NodeP b)
{
auto A = a->dist_store_down - a->dist_up;
auto B = b->dist_store_down - b->dist_up;
return A < B ? a : b;
}
template<NodeP comb(NodeP,NodeP)>
struct sparsetable
{
using T = NodeP;
std::vector<std::vector<T>> data;
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)]);
}
};
sparsetable<lowHeight> sp;
void make_hld(NodeP n)
{
std::vector<NodeP> v;
std::vector<NodeP> o;
while(n)
{
v.push_back(n);
for(auto[c,_] : n->c) if(c!=n->heavyc) o.push_back(c);
n=n->heavyc;
}
auto sp = new sparsetable<mincombD>(v);
for(int i = 0; i < v.size(); i++)
{
v[i]->heavy = sp;
v[i]->heavy_idx = i;
}
for(auto n : o) make_hld(n);
}
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);
make_hld(e);
// std::cout << e << "\n";
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;
NodeP mind = R;
auto p = R;
// while(p != cut)
// {
// d+=p->p_d;
// p=p->p;
// mind = mincombD(mind,p->dist_store_down+d);
// };
while(p->heavy!=cut->heavy)
{
mind = mincombD(mind,p->heavy->query(0,p->heavy_idx+1));
p = p->heavy->query(0,1)->p;
}
// unsigned int hd = R->height-cut->height;
// for(int s = log2(hd);s >= 0; s--)
// {
// if(p->par.size()<=s) continue;
// if(p->par[s].first->height >= cut->height)
// {
// mind = mincombD(mind,p->par[s].second);
// p = p->par[s].first;
// }
// }
mind = mincombD(mind,p->heavy->query(cut->heavy_idx,p->heavy_idx+1));
result.push_back(mind->dist_store_down-mind->dist_up+R->dist_up);
}
for(auto i : result)
{
if(i==-2) std::cout << "oo\n";
else if (i==-1) std::cout << "escaped\n";
else std::cout << i << "\n";
}
}
