stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
/*

    SPFA ````

*/



#include <iostream>

#include <cstring>

#include <algorithm>

#include <queue>



using namespace std;

typedef long long ll;

const int N = 1e6+10;

int n,m,k,q,x,y;

int h[N],w[N],e[N],ne[N],idx;



ll dist[N];

bool st[N];



void add(int a,int b,int c)

{

    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;

}



void spfa()

{

    memset(dist,0x3f,sizeof dist);

    dist[k] = 0;

    queue<int>q;

    q.push(k);

    

    st[k] = true;

    

    while(q.size())

    {

        int t = q.front();

        q.pop();

        

        st[t] = false;

        

        for(int i = h[t];i!=-1;i=ne[i])

        {

            int j = e[i];

            if(dist[j]>dist[t] + w[i])

            {

                dist[j] = dist[t] + w[i];

                if(!st[j])

                {

                    q.push(j);

                    st[j] = true;

                }

            }



        }

    }

}



int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);cout.tie(0);

    cin >>n;

    memset(h,-1,sizeof h);

    m = n-1;

    while(m--)

    {

        int a,b,c;

        cin >>a>>b>>c;

        add(a,b,c);

        add(b,a,c);

    }

    

    cin >> q>>k;

    spfa();

    while(q--)

    {

        cin >>x >>y;

        cout << dist[x] + dist[y] << endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.82473151323366x):
#include <bits/stdc++.h>

#define ll long long

#define pll pair<ll,ll>

#define pb push_back

#define ff first

#define ss second

using namespace std;

vector<pll>vec[100005];

ll dist[100005];

void dfs(ll node,ll parent,ll value)

{

    dist[node]=value;

    for(auto i:vec[node]){

        if(i.ff==parent)continue;

        dfs(i.ff,node,value+i.ss);

    }

    return;

}

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    ll n,a,b,c,q,k;

    cin>>n;

    for(int i=1;i<=n-1;i++){

        cin>>a>>b>>c;

        vec[a].pb({b,c});

        vec[b].pb({a,c});

    }

    cin>>q>>k;

    dfs(k,-1,0);

    while(q--){

        cin>>a>>b;

        cout<<dist[a]+dist[b]<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



const int limit = 100010;

using edge = struct {int to; long long cost;};

vector<edge> tree[limit];

long long depth[limit];



void dfs(int v, int p, long long d){

    depth[v] = d;

    for(auto &e : tree[v]) {

        if(e.to == p) continue;

        dfs(e.to, v, d + e.cost);

    }

}



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);



    int n;

    cin >> n;



    for(int i = 0; i < n-1; i++){

        int a, b, c;

        cin >> a >> b >> c;

        a--, b--;

        tree[a].push_back({b, c});

        tree[b].push_back({a, c});

    }



    int q, k;

    cin >> q >> k;

    k--;



    dfs(k, -1, 0);



    for(int i = 0; i < q; i++){

        int x, y;

        cin >> x >> y;

        x--, y--;

        cout << depth[x] + depth[y] << endl;

    }



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.454690005886448x):
#include "bits/stdc++.h"

#define rep(i,n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef long long int ll;

typedef pair<int, int> P;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }





struct State{

    int at;

    ll cost;

    State(int a, ll c) : at(a), cost(c){}

    bool operator>(const State& s) const{

        return cost > s.cost;

    }

};



struct Edge{

    int to;

    ll cost;

    Edge(int t, ll c) : to(t), cost(c){}

};



using Graph = vector<vector<Edge> >;

const ll INF = 1e15;



void dijkstra(int s, const Graph& G, vector<ll>& minc){

    minc.assign(G.size(), INF);

    priority_queue<State, vector<State>, greater<State> > pq;

    pq.emplace(s, 0);

    minc[s] = 0;

    while(!pq.empty()){

        State cur = pq.top();

        pq.pop();

        if(minc[cur.at] < cur.cost) continue;

        for(const Edge& e : G[cur.at]){

            ll cost = cur.cost + e.cost;

            if(minc[e.to] <= cost) continue;

            minc[e.to] = cost;

            pq.emplace(e.to, cost);

        }

    }

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    Graph G(n);

    rep(i,n-1){

        int a, b;

        ll c;

        cin >> a >> b >> c;

        --a; --b;

        G[a].push_back(Edge(b, c));

        G[b].push_back(Edge(a, c));

    }

    int q, k;

    cin >> q >> k;

    --k;

    vector<ll> minc(n, INF);

    dijkstra(k, G, minc);

    rep(i,q){

        int x, y;

        cin >> x >> y;

        --x; --y;

        cout << minc[x] + minc[y] << endl;

    }

    return 0;

}
// Slower C++ solution:
#include "bits/stdc++.h"

#define rep(i,n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef long long int ll;

typedef pair<int, int> P;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



const int limit = 100005;

using edge = struct {int to; long long cost;};



int n;

vector<edge> tree[limit];

vector<long long> dist;



void dfs(int v, long long d = 0, int p = -1){

    dist[v] = d;

    for(auto &e : tree[v]) {

        if(e.to == p) continue;

        dfs(e.to, d + e.cost, v);

    }

}



vector<long long> calcDist(int s){

    dist = vector<long long>(n);

    dfs(s);

    return dist;

}



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    cin >> n;

    for(int i = 0; i < n-1; i++){

        int a, b;

		ll c;

        cin >> a >> b >> c;

        a--, b--;

        tree[a].push_back({b, c});

        tree[b].push_back({a, c});

    }

	int q, k;

	cin >> q >> k;

	k--;

	vector<ll> distK = calcDist(k);

	rep(i,q){

		int x, y;

		cin >> x >> y;

		x--; y--;

		ll ans = dist[x] + dist[y];

		cout << ans << endl;

	}

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.465845443692141x):
#include "bits/stdc++.h"

#define rep(i,n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef long long int ll;

typedef pair<int, int> P;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }





struct State{

    int at;

    ll cost;

    State(int a, ll c) : at(a), cost(c){}

    bool operator>(const State& s) const{

        return cost > s.cost;

    }

};



struct Edge{

    int to;

    ll cost;

    Edge(int t, ll c) : to(t), cost(c){}

};



using Graph = vector<vector<Edge> >;

const ll INF = 1e15;



void dijkstra(int s, const Graph& G, vector<ll>& minc){

    minc.assign(G.size(), INF);

    priority_queue<State, vector<State>, greater<State> > pq;

    pq.emplace(s, 0);

    minc[s] = 0;

    while(!pq.empty()){

        State cur = pq.top();

        pq.pop();

        if(minc[cur.at] < cur.cost) continue;

        for(const Edge& e : G[cur.at]){

            ll cost = cur.cost + e.cost;

            if(minc[e.to] <= cost) continue;

            minc[e.to] = cost;

            pq.emplace(e.to, cost);

        }

    }

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    Graph G(n);

    rep(i,n-1){

        int a, b;

        ll c;

        cin >> a >> b >> c;

        --a; --b;

        G[a].push_back(Edge(b, c));

        G[b].push_back(Edge(a, c));

    }

    int q, k;

    cin >> q >> k;

    --k;

    vector<ll> minc(n, INF);

    dijkstra(k, G, minc);

    rep(i,q){

        int x, y;

        cin >> x >> y;

        --x; --y;

        cout << minc[x] + minc[y] << endl;

    }

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



const int MAX = 1e5 + 10;

int n;

int q, k;

vector<pair<int, long long>> G[MAX];

long long minDist[MAX];



int main() {

  scanf("%d", &n);

  for (int i = 0; i < n - 1; i++) {

    int a, b, c;;

    scanf("%d%d%d", &a, &b, &c);

    a--;b--;

    G[a].emplace_back(make_pair(b, c));

    G[b].emplace_back(make_pair(a, c));

  }

  scanf("%d%d", &q, &k);

  k--;

  fill(minDist, minDist + MAX, 1e18);

  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

  pq.push({0, k});

  minDist[k] = 0;

  while (!pq.empty()) {

    auto now = pq.top(); pq.pop();

    for (auto nxt : G[now.second]) {

      const long long nxtCost = now.first + nxt.second;

      if (minDist[nxt.first] <= nxtCost) {

        continue;

      }

      minDist[nxt.first] = nxtCost;

      pq.push({nxtCost, nxt.first});

    }

  }

  for (int i = 0; i < q; i++) {

    cerr << "problem " << i + 1 << " solved" << endl;

    int x, y;

    scanf("%d%d", &x, &y);

    x--;y--;

    cout << minDist[x] + minDist[y] << endl;

  }

  

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.3037768196328585x):
#include <bits/stdc++.h>



using namespace std;



template<typename T = int>

vector<T> dijkstra(const vector<vector<pair<int, T>>> &G, int st, const T inf) {

    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;

    pq.push({0, st});

    vector<T> dist(G.size(), inf);

    dist[st] = 0;

    while (!pq.empty()) {

        const auto now = pq.top();

        pq.pop();

        for (auto nxt : G[now.second]) {

            const T nextCost = now.first + nxt.second;

            if (dist[nxt.first] <= nextCost) {

                continue;

            }

            dist[nxt.first] = nextCost;

            pq.push(make_pair(nextCost, nxt.first));

        }

    }

    return dist;

}



int main() {

    int n;

    cin >> n;

    vector<vector<pair<int, long long>>> Graph(n);

    for (int i = 0; i < n - 1; i++) {

        int a, b;

        long long c;

        cin >> a >> b >> c;

        a--;

        b--;

        Graph[a].emplace_back(make_pair(b, c));

        Graph[b].emplace_back(make_pair(a, c));

    }

    int q, k;

    cin >> q >> k;

    k--;

    vector<long long> dist = dijkstra<long long>(Graph, k, (long long) 1e18);

    for (int i = 0; i < q; i++) {

        int x, y;

        cin >> x >> y;

        x--;y--;

        cout << dist[x] + dist[y] << endl;

    }

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

int64_t INF = 1000000000000000;

int64_t MAXN = 100010;

int64_t N, Q, K, a, b, c, x, y;

vector<vector<pair<int64_t, int64_t>>> Graph(MAXN);

vector<int64_t> Color(MAXN, 0), D(MAXN, INF); // 各点を無限大にする。



void dijkstra()

{

  priority_queue<pair<int64_t, int64_t>, vector<pair<int64_t, int64_t>>, greater<pair<int64_t, int64_t>>> PQ;



  D.at(K) = 0; // 始点を0とする。

  PQ.push(make_pair(0, K));

  Color.at(K) = 1; // グレーの状態に



  while (!PQ.empty())

  {

    pair<int64_t, int64_t> f = PQ.top();

    PQ.pop();

    int64_t u = f.second; // 未決定の中で、最短経路の頂点

    Color.at(u) = 2;      // 決定済とする

    if (D.at(u) < f.first)

      continue;

    for (int i = 0; i < Graph.at(u).size(); i++)

    {

      int64_t v = Graph.at(u).at(i).first; // uからの辺の終点

      if (Color.at(v) == 2)

        continue;

      if (D.at(v) > D.at(u) + Graph.at(u).at(i).second) // uを経由した場合の距離

      {

        D.at(v) = D.at(u) + Graph.at(u).at(i).second;

        PQ.push(make_pair(D.at(v), v)); // 頂点vの暫定での距離、頂点vをペアにする

        Color.at(v) = 1;                // グレーにする

      }

    }

  }

}



int main()

{

  cin >> N;

  for (int i = 0; i < N - 1; i++)

  {

    cin >> a >> b >> c;

    Graph.at(a).push_back(make_pair(b, c));

    Graph.at(b).push_back(make_pair(a, c));

  }

  cin >> Q >> K;

  vector<pair<int64_t, int64_t>> vp(Q);

  for (int i = 0; i < Q; i++)

  {

    cin >> x >> y;

    vp.at(i) = make_pair(x, y);

  }

  dijkstra();

  for (auto p : vp)

  {

    tie(x, y) = p;

    cout << D.at(x) + D.at(y) << endl;

  }

}


// Faster C++ solution for the same problem (measured speedup: 1.2494497920416536x):
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

typedef pair<int64_t, int64_t> P;

vector<P> to[MAXN];

vector<int64_t> d(MAXN, -1);



void dfs(int v)

{

  for (auto u : to[v])

  {

    if (d.at(u.first) == -1)

    {

      d.at(u.first) = d.at(v) + u.second;

      dfs(u.first);

    }

  }

}



int main()

{

  int64_t N, a, b, c;

  cin >> N;

  for (int i = 0; i < N - 1; i++)

  {

    cin >> a >> b >> c;

    a--, b--;

    to[a].emplace_back(b, c);

    to[b].emplace_back(a, c);

  }

  int Q, K, x, y;

  cin >> Q >> K;

  K--;

  d[K] = 0;

  dfs(K);

  for (int i = 0; i < Q; i++)

  {

    cin >> x >> y;

    x--, y--;

    cout << d[x] + d[y] << endl;

  }

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <queue>

#include <map>

#include <list>

#include <deque>

#include <string>

#include <algorithm>

#include <cmath>

using namespace std;

#define dump(a) cout << (a) << endl;

typedef long long ll;

ll mod = 1e9+7;



int n;

vector<pair<int, ll>> edge[100001];

bool node[100001];

int q, k;



void dfs( int x, ll cost, ll d[] ) {

    if( node[x] ) return;

    node[x] = true;

    d[x] = cost;

    for( int i = 0; i < (int)edge[x].size(); i++ ) dfs( edge[x][i].first, cost+edge[x][i].second, d );

}



int main() {

    cin >> n;

    for( int i = 0; i < n-1; i++ ) {

        int a, b, c;

        cin >> a >> b >> c;

        edge[a].push_back( make_pair( b, c ) );

        edge[b].push_back( make_pair( a, c ) );

    }

    for( int i = 1; i <= n; i++ ) node[i] = false;

    cin >> q >> k;

    ll d[100001] = {};

    dfs( k, 0 , d);

    for( int i = 0; i < q; i++ ) {

        int a, b;

        cin >> a >> b;

        dump( d[a]+d[b] );

    }

    return 0;  

}

// Faster C++ solution for the same problem (measured speedup: 1.2421041443272627x):
#include <bits/stdc++.h>

using namespace std;



#define rep(i, n) for (Int i = 0; i < (Int)n; i++)

#define rep2(i, s, n) for (Int i = s; i < (Int)(n); i++)

#define rep3(i, n, s) for (Int i = n - 1; i >= s; i--)

#define dump(x) cout << (x) << '\n'

#define Int int64_t

#define fi first

#define se second

#define all(x) (x).begin(), (x).end()

#define rall(x) (x).rbegin(), (x).end()

 

double EPS = 1e-10;

Int INF = 1e18;

int inf = 1e9;

Int mod = 1e9+7;



vector<pair<Int, Int>> G[100001];



vector<Int> dijkstra(vector<pair<Int, Int>> G[], Int n, Int s) {

    vector<Int> dist(n, INF);

    priority_queue<pair<Int, Int>, vector<pair<Int, Int>>, greater<pair<Int, Int>>> q;

    q.push({0, s});

    dist[s] = 0;

    while (not q.empty()) {

        pair<Int, Int> p = q.top();

        q.pop();

        Int cur = p.se;

        if (dist[cur] < p.fi) continue;

        rep(i, G[cur].size()) {

            Int to = G[cur][i].fi;

            Int cost = G[cur][i].se;

            if (dist[to] > dist[cur] + cost) {

                dist[to] = dist[cur] + cost;

                q.push({dist[to], to});

            }

        }

    }

    return dist;

}



int main() {

    Int n;

    cin >> n;

    rep(i, n - 1) {

        Int a, b, c;

        cin >> a >> b >> c;

        a--, b--;

        G[a].emplace_back(b, c);

        G[b].emplace_back(a, c);

    }

    Int q, k;

    cin >> q >> k;

    k--;

    vector<Int> d = dijkstra(G, n, k);

    // rep(i, n) dump(d[i]);

    rep(i, q) {

        Int x, y;

        cin >> x >> y;

        x--, y--;

        dump(d[x] + d[y]);

    }

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <queue>



using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

static const int MAX = 100001;



int N;

vector<P> G[MAX];

ll cost[MAX];

void bfs(int k);



int main() {



    cin >> N;



    ll a, b, c;

    for (int i = 0; i < N-1; i++) {

        cin >> a >> b >> c;

        G[a].push_back(make_pair(b, c));

        G[b].push_back(make_pair(a, c));

    }



    int Q, K;

    cin >> Q >> K;



    bfs(K);



    int x, y;

    for (int i = 0; i < Q; i++) {

        cin >> x >> y;

        cout << cost[x] + cost[y] << '\n';

    }

}



void bfs(int k) {



    queue<int> q;

    q.push(k);

    ll u;

    cost[k] = 0;

    while (!q.empty()) {

        u = q.front(); q.pop();

        for (int v = 0; v < G[u].size(); v++) {

            P p = G[u][v];

            int next_node = p.first, next_cost = p.second;

            if (cost[next_node] != 0) continue;

            cost[next_node] += cost[u] + next_cost;

            q.push(next_node);

        }

    }

}


// Faster C++ solution for the same problem (measured speedup: 3.4830364455547107x):
#include <bits/stdc++.h>

using namespace std;

/* typedef */

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

/* constant */

const int INF = 1 << 30;

const ll LINF = 1LL << 50;

const int NIL = -1;

const int MAX = 10000;

const int mod = 1000000007;

const double pi = 3.141592653589;

/* global variables */

/* function */

/* main */

int main(){

    int N;

    cin >> N;

    vector<vector<pll> > G(N, vector<pll>());

    ll a, b, c;

    for (int i = 0; i < N-1; i++) {

        cin >> a >> b >> c;

        a--, b--;

        G[a].push_back(pii(b, c));

        G[b].push_back(pii(a, c));

    }

    int Q, K;

    cin >> Q >> K;

    K--;

    queue<int> q;

    vector<ll> d(N, -1);

    q.push(K);

    d[K] = 0;

    while (!q.empty()) {

        int from = q.front();

        q.pop();

        for (pll p : G[from]) {

            int to = p.first;

            ll w = p.second;

            if (d[to] != -1) continue;

            d[to] = d[from] + w;

            q.push(to);

        }

    }

    for (int i = 0; i < Q; i++) {

        cin >> a >> b;

        a--, b--;

        cout << d[a] + d[b] << '\n';

    }

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)

#define rep(i,n) REP(i,0,n)

#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)

#define ALLOF(c) (c).begin(), (c).end()

typedef long long ll;

typedef unsigned long long ull;



vector<pair<ll,ll>> GG[100005];

ll dist[100005];



int N;

vector<int> G[100005];

int parent[64][100005];

int depth[100005];

void dfs(int v, int p, int d){

  parent[0][v] = p;

  depth[v] = d;

  for(int i=0; i<G[v].size(); i++){

    if(G[v][i] != p) dfs(G[v][i], v, d+1);

  }

}

void init(int root){

  dfs(root, -1, 0);

  for(int k=0; k+1<64; k++){

    for(int v=0; v<N+1; v++){

      if(parent[k][v] < 0) parent[k+1][v] = -1;

      else parent[k+1][v] = parent[k][parent[k][v]];

    }

  }

}

int lca(int u, int v){

  if(depth[u] > depth[v]) swap(u, v);

  for(int k=0; k<64; k++){

    if((depth[v] - depth[u]) >> k & 1){

      v = parent[k][v];

    }

  }

  if(u==v) return u;

  for(int k=64-1; k>=0; k--){

    if(parent[k][u] != parent[k][v]){

      u = parent[k][u];

      v = parent[k][v];

    }

  }

  return parent[0][u];

}





void calc_dist(ll v, ll d){

  if(dist[v] != -1) return;

  dist[v] = d;

  rep(i,GG[v].size()){

    calc_dist(GG[v][i].first, d+GG[v][i].second);

  }

}



ll calc(int root, int x, int y){

  int z = lca(x, y);

  return abs(dist[z]-dist[x]) + abs(dist[z]-dist[y]);

}



int main(){

  cin >> N;

  rep(i,N-1){

    ll a, b, c;

    cin >> a >> b >> c;

    a--;

    b--;

    G[a].push_back(b);

    G[b].push_back(a);

    GG[a].emplace_back(b,c);

    GG[b].emplace_back(a,c);

  }



  rep(i,100005) dist[i] = -1;

  

  ll root = -1;

  rep(i,N){

    if(G[i].size() == 1) root = i;

  }

  init(root);

  calc_dist(root, 0);



  int Q, K;

  cin >> Q >> K;

  K--;

  rep(i,Q){

    int x, y;

    cin >> x >> y;

    x--;

    y--;

    cout << calc(root, x, K) + calc(root, K, y) << endl;

  }

  

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.669531204562588x):
#include <bits/stdc++.h>

using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)

#define rep(i,n) REP(i,0,n)

#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)

#define ALLOF(c) (c).begin(), (c).end()

typedef long long ll;

typedef unsigned long long ull;



vector<pair<ll,ll>> G[100005];

ll dist[100005];



void calc_dist(ll v, ll d){

  if(dist[v] != -1) return;

  dist[v] = d;

  rep(i,G[v].size()){

    calc_dist(G[v][i].first, d+G[v][i].second);

  }

}



int main(){

  int N;

  cin >> N;

  rep(i,N-1){

    ll a, b, c;

    cin >> a >> b >> c;

    a--;

    b--;

    G[a].emplace_back(b,c);

    G[b].emplace_back(a,c);

  }



  rep(i,100005) dist[i] = -1;

  

  int Q, K;

  cin >> Q >> K;

  K--;



  calc_dist(K, 0);



  

  rep(i,Q){

    int x, y;

    cin >> x >> y;

    x--;

    y--;

    cout << dist[x] + dist[y] << endl;

  }

  

  return 0;

}
// Slower C++ solution:
#include "bits/stdc++.h"

#define MOD 1000000007

#define INF 1123456789012345

#define in std::cin

#define out std::cout

#define rep(i,N) for(int i=0;i<N;++i)

typedef long long int LL;

typedef std::pair<LL, LL> P;

struct edge { LL to, cost; };



LL N, a[112345], b[112345], c[112345], Q, K, x[112345], y[112345];

LL d[112345];

std::vector<edge>G[112345];



void dijkstra(LL s)

{

	std::priority_queue<P, std::vector<P>, std::greater<P>>que;

	std::fill(d, d + N + 1, INF);

	d[s] = 0;

	que.push(P(0, s));

	while (!que.empty())

	{

		P p = que.top(); que.pop();

		LL v = p.second;

		if (d[v] < p.first) { continue; }

		rep(i, G[v].size())

		{

			edge e = G[v][i];

			if (d[e.to] > d[v] + e.cost)

			{

				d[e.to] = d[v] + e.cost;

				que.push(P(d[e.to], e.to));

			}

		}

	}

}



int main()

{

	in >> N;

	rep(i, N - 1)

	{

		in >> a[i] >> b[i] >> c[i];

		G[a[i]].push_back({ b[i],c[i] });

		G[b[i]].push_back({ a[i],c[i] });

	}

	in >> Q >> K;

	rep(i, Q) { in >> x[i] >> y[i]; }



	dijkstra(K);



	rep(i, Q) { out << d[x[i]] + d[y[i]] << std::endl; }

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.782384556502912x):
#include "bits/stdc++.h"

#define in std::cin

#define out std::cout

#define rep(i,N) for(int i=0;i<N;++i)

typedef long long int LL;

typedef std::pair<LL, LL> P;

struct edge { LL to, cost; };



const LL inf = 112345678901234;

LL N, Q, K;

std::vector<LL>dist;

std::vector<std::vector<edge>>G;



void dijkstra(LL s)

{

	std::priority_queue<P, std::vector<P>, std::greater<P>>que;

	std::fill(dist.begin(), dist.end(), inf);

	dist[s] = 0;

	que.push(P(0, s));

	while (!que.empty())

	{

		P p = que.top(); que.pop();

		LL v = p.second;

		if (dist[v] < p.first) { continue; }

		rep(i, G[v].size())

		{

			edge e = G[v][i];

			if (dist[e.to] > dist[v] + e.cost)

			{

				dist[e.to] = dist[v] + e.cost;

				que.push(P(dist[e.to], e.to));

			}

		}

	}

}



int main()

{

	in >> N;

	std::vector<LL>a(N - 1), b(N - 1), c(N - 1);

	dist.resize(N + 1); G.resize(N + 1);

	rep(i, N - 1)

	{

		in >> a[i] >> b[i] >> c[i];

		G[a[i]].push_back({ b[i],c[i] });

		G[b[i]].push_back({ a[i],c[i] });

	}

	in >> Q >> K;

	dijkstra(K);

	std::vector<LL> x(Q), y(Q);

	rep(i, Q)

	{

		in >> x[i] >> y[i];

		out << dist[x[i]] + dist[y[i]] << std::endl;

	}

	return 0;

}