You are given a tree with N vertices.

Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices.

The i-th edge (1≤i≤N-1) connects Vertices a_i and b_i, and has a length of c_i.
You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):
 - find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K.

-----Constraints-----
 - 3≤N≤10^5 
 - 1≤a_i,b_i≤N (1≤i≤N-1) 
 - 1≤c_i≤10^9 (1≤i≤N-1) 
 - The given graph is a tree.
 - 1≤Q≤10^5 
 - 1≤K≤N 
 - 1≤x_j,y_j≤N (1≤j≤Q) 
 - x_j≠y_j (1≤j≤Q) 
 - x_j≠K,y_j≠K (1≤j≤Q) 

-----Input-----
Input is given from Standard Input in the following format:  
N  
a_1 b_1 c_1  
:  
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:  
x_{Q} y_{Q}

-----Output-----
Print the responses to the queries in Q lines.

In the j-th line j(1≤j≤Q), print the response to the j-th query.

-----Sample Input-----
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

-----Sample Output-----
3
2
4

The shortest paths for the three queries are as follows:
 - Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3 
 - Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2 
 - Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4

Difficulty: interview

Starter code:

Solutions:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = MAP()
        adj[a-1].append([b-1, c])
        adj[b-1].append([a-1, c])

    Q, K = MAP()
    K -= 1

    d = [inf]*N
    d[K] = 0
    que = []
    heappush(que, K)

    while que:
        v = heappop(que)
        for b, c in adj[v]:
            if d[b] > d[v] + c:
                d[b] = d[v] + c
                heappush(que, b)

    for i in range(Q):
        x, y = MAP()
        print(d[x-1]+d[y-1])

def __starting_point():
    solve()
__starting_point()

import sys
def input():return sys.stdin.readline().strip()
from collections import deque

def main():
    N = int(input())
    info = [tuple(map(int, input().split())) for _ in range(N-1)]
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    to = [[] for _ in range(N)]
    for a, b, c in info:
        a -= 1
        b -= 1
        to[a].append((b, c))
        to[b].append((a, c))
    
    INF = 10**18
    dist = [INF]*N
    def dfs(s):
        stack = deque()
        push = stack.append
        pop = stack.pop

        dist[s] = 0
        push(s)

        while stack:
            now = pop()
            now_cost = dist[now]

            for nv, c in to[now]:
                if dist[nv] != INF:
                    continue
                dist[nv] = now_cost + c
                push(nv)


    # query
    K -= 1
    dfs(K)
    ans = []
    for x, y in queries:
        x -= 1
        y -= 1
        xy = dist[x] + dist[y]
        ans.append(xy)

    print(*ans, sep="\n")
def __starting_point():
    main()
__starting_point()

import sys
from collections import defaultdict
from heapq import heappush, heappop


def input():
    return sys.stdin.readline().strip()


def dijkstra(adj_list, start):
    n = len(adj_list)
    dist = [float("inf")] * n
    dist[start] = 0

    pq = []
    heappush(pq, (0, start))
    visited = set()
    while pq:
        w, v = heappop(pq)
        if dist[v] < w:
            continue
        visited.add(v)
        for nv, nw in adj_list[v]:
            if nv in visited:
                continue
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq, (dist[nv], nv))
    return dist


N = int(input())
g = defaultdict(list)
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    g[a].append((b, c))
    g[b].append((a, c))
Q, K = list(map(int, input().split()))
K -= 1
d = dijkstra(g, K)
ans = []
for _ in range(Q):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1
    print((d[x] + d[y]))


N = int(input())
f = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    f[a-1].append([b-1,c])
    f[b-1].append([a-1,c])
from collections import deque
d = deque()
s = [-1]*N
Q,K = map(int,input().split())
d.append(K-1)
s[K-1] = 0
while len(d) > 0:
    z = d.popleft()
    for i,j in f[z]:
        if s[i] == -1:
            s[i] = j+s[z]
            d.append(i)
for i in range(Q):
    x,y = map(int,input().split())
    print(s[x-1]+s[y-1])

import sys

sys.setrecursionlimit(200000)

n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
q,k = list(map(int,input().split()))
k -= 1
#kからの距離
tree = [[] for _ in range(n)]
for a,b,c in l:
    a -= 1
    b -= 1
    tree[a].append([b,c])
    tree[b].append([a,c])

bit = [0 for _ in range(n)]
depth = [0 for _ in range(n)]
def dfs(v,d=0):
    bit[v] = 1
    depth[v] = d
    for j,k in tree[v]:
        if bit[j]==0:
            dfs(j,d+k)
dfs(k)

for _ in range(q):
    x,y = list(map(int,input().split()))
    x-= 1
    y-= 1
    print((depth[x] + depth[y]))


from collections import defaultdict,deque
import sys
finput=lambda: sys.stdin.readline().strip()

def main():
  n=int(finput())
  edges=[tuple(map(int,finput().split())) for _ in range(n-1)]
  q,k=list(map(int,finput().split()))
  xy=[tuple(map(int,finput().split())) for _ in range(q)]
  ed=defaultdict(deque)
  wt=defaultdict(int)
  for e in edges:
    ed[e[0]].append(e[1])
    ed[e[1]].append(e[0])
    wt[(e[0],e[1])]=e[2]
    wt[(e[1],e[0])]=e[2]
  stack=deque([k])
  cv=stack[0]
  dist=defaultdict(int)
  while stack:
    while ed[cv]:
      if cv!=k:
        if ed[cv][-1]==stack[-1]:
          ed[cv].pop()
          if not ed[cv]:
            break
      stack.append(cv)
      cv=ed[cv].pop()
      dist[cv]=dist[stack[-1]]+wt[(stack[-1],cv)]
    cv=stack.pop()
  for que in xy:
    print((dist[que[0]]+dist[que[1]]))

def __starting_point():
    main()

__starting_point()

F=lambda:map(int,input().split())
N=int(input())

G=[[]for _ in range(N+1)]
for _ in range(N-1):
    a,b,c=F()
    G[a].append([a,b,c])
    G[b].append([b,a,c])

Q,K=F()

D=[10**9*(N+1)]*(N+1)
D[0]=0
D[K]=0
from collections import*
que=deque(G[K])
while que:
    a,b,c=que.popleft()
    if D[a]+c<D[b]:
        D[b]=D[a]+c
        for g in G[b]:
            que.append(g)

for _ in range(Q):
    x,y=F()
    print(D[x]+D[y])

N = int(input())
G = [[] for n in range(N)]

for n in range(N-1):
  a,b,c = map(int,input().split())
  G[a-1].append((b-1,c))
  G[b-1].append((a-1,c))

Q,K = map(int,input().split())
d = N*[-1]
d[K-1] = 0
q = [K-1]

while q:
  t = q.pop()
  for b,c in G[t]:
    if d[b]==-1:
      d[b] = d[t]+c
      q.append(b)

for q in range(Q):
  x,y = map(int,input().split())
  print(d[x-1]+d[y-1])

F=lambda:map(int,input().split())
N=int(input())
abc=[[*F()]for _ in range(N-1)]
Q,K=F()
xy=[[*F()]for _ in range(Q)]

G=[[]for _ in range(N+1)]
for a,b,c in abc:
    G[a].append([a,b,c])
    G[b].append([b,a,c])

D=[10**9*(N+1)]*(N+1)
D[0]=0
D[K]=0
from collections import*
que=deque(G[K])
while que:
    a,b,c=que.popleft()
    if D[a]+c<D[b]:
        D[b]=D[a]+c
        for g in G[b]:
            que.append(g)

for x,y in xy:
    print(D[x]+D[y])

from collections import deque

N = int(input())
A = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]

d = [[] for _ in range(N)]
for a, b, c in A:
    d[a-1].append([b-1, c])
    d[b-1].append([a-1, c])

c = [0]*N
f = [False]*N
f[K-1] = True

q = deque([K-1])
while q:
    now = q.popleft()
    for nex, cost in d[now]:
        if f[nex]:
            continue
        c[nex] = c[now]+cost
        f[nex] = True
        q.append(nex)

for x, y in X:
    print(c[x-1]+c[y-1])

# 深さ優先探索
N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    links[a].append((b, c))
    links[b].append((a, c))

Q, K = list(map(int, input().split()))

d = [float('inf')] * (N + 1)
d[K] = 0
q = [K]
while q:
    i = q.pop()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = list(map(int, input().split()))
    result.append(d[x] + d[y])
print(('\n'.join(str(v) for v in result)))
#print(*result, sep='\n')


def abc070_d():
    import sys
    sys.setrecursionlimit(10010010)
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    n = next(inp)
    adjlist = [[] for _ in range(n)]
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjlist[a].append((b, c))
        adjlist[b].append((a, c))

    q = next(inp)
    k = next(inp) - 1

    dist = [-1] * n

    def dfs(x:int, d:int):
        dist[x] = d
        for nx, nd in adjlist[x]:
            if dist[nx] != -1: continue
            dfs(nx, d + nd)

    dfs(k, 0)

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = dist[x] + dist[y]
        print(ans)

def __starting_point():
    abc070_d()
__starting_point()

import sys
sys.setrecursionlimit(10**7)

def dfs(st, depth=0):
    dist[st] = depth
    for to, c in tree[st]:
        if dist[to]>=0:
            continue
        dfs(to, depth+c)


N = int(input())
tree = [[] for _ in range(N)]
dist = [-1]*N

for _ in range(N-1):
    a,b,c = map(int, input().split())
    tree[a-1].append((b-1, c))
    tree[b-1].append((a-1, c))

Q, K = map(int, input().split())
dfs(K-1, 0)
# print(dist)
# print(tree)
for _ in range(Q):
    x, y = map(int, input().split())
    print(dist[x-1]+dist[y-1])

n=int(input())
abc=[[] for _ in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    abc[a].append([b,c])
    abc[b].append([a,c])
from collections import deque
q,k=map(int,input().split())
visited=[0]*(n+1)
distance=[0]*(n+1)
que=deque()
que.append(k)
visited[k]+=1
count=0
while que:
    x=que.pop()
    for y in abc[x]:
        if visited[y[0]]==0:
            distance[y[0]]+=distance[x]+y[1]
            visited[y[0]]+=1
            que.appendleft(y[0])
for j in range(q):
    c,d=map(int,input().split())
    print(distance[c]+distance[d])

def main():
    from collections import defaultdict
    from heapq import heappop, heappush
    N = int(input())
    edge = defaultdict(list)
    length = defaultdict(lambda : defaultdict(lambda : 10**20))
    
    for i in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        if b<a:
            a,b = b,a
        length[a][b] = c
    Q,K = map(int,input().split())
    K -= 1
    cost = [0]*N
    length[K][K] = 0
    targets = [(0,K)]
    cost = [10**18]*N
    cost[K] = 0
    visited = [False]*N
    while targets:
        c,t = heappop(targets)
        if visited[t]:
            continue
        cost[t] = c
        visited[t] = True
        for v in edge[t]:
            if cost[v] > cost[t] + length[min(t,v)][max(t,v)]:
                heappush(targets,(cost[t] + length[min(t,v)][max(t,v)],v))

    out = []
    for i in range(Q):
        x,y = map(lambda x: int(x)-1, input().split())
        out.append(cost[x]+cost[y])

    print('\n'.join(map(str,out)))







main()

import sys
from collections import deque

N = int(sys.stdin.readline())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, sys.stdin.readline().split())
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))

Q, K = map(int, sys.stdin.readline().split())

# Kを始点とする、各点までの距離
dist = [-1 for _ in range(N)]

visited = set()
q = deque([(K-1, 0)])
while q:
    p, c = q.popleft()
    if p in visited:
        continue
    dist[p] = c

    visited.add(p)
    for (next_p, next_c) in edges[p]:
        q.append((next_p, c + next_c))
# print(dist)

for _ in range(Q):
    x, y = map(int, sys.stdin.readline().split())
    print(dist[x-1] + dist[y-1])

N=int(input())
G=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    G[a].append([b,c])
    G[b].append([a,c])
Q,K=map(int,input().split())
K-=1
dist=[-1 for _ in range(N)]
dist[K]=0
q=[K]
while len(q)>0:
    v=q.pop()
    for p in G[v]:
        nv=p[0]
        if dist[nv]!=-1:
            continue
        dist[nv]=dist[v]+p[1]
        q.append(nv)
for _ in range(Q):
    x,y=map(int,input().split())
    print(dist[x-1]+dist[y-1])

from collections import deque
#
# N = 5
# ARR = [
#     [1, 2, 1],
#     [1, 3, 1],
#     [2, 4, 1],
#     [3, 5, 1]
# ]
#
# Q, K = 3, 1
#
# BRR = [
#     [2, 4],
#     [2, 3],
#     [4, 5],
# ]
#
#
# N = 7
# ARR = [
#     [1, 2, 1],
#     [1, 3, 3],
#     [1, 4, 5],
#     [1, 5, 7],
#     [1, 6, 9],
#     [1, 7, 11],
# ]
#
# Q, K = 3, 2
#
# BRR = [
#     [1, 3],
#     [4, 5],
#     [6, 7],
# ]
#
#
# N = 10
# ARR = [
#     [1, 2, 1000000000],
#     [2, 3, 1000000000],
#     [3, 4, 1000000000],
#     [4, 5, 1000000000],
#     [5, 6, 1000000000],
#     [6, 7, 1000000000],
#     [7, 8, 1000000000],
#     [8, 9, 1000000000],
#     [9, 10, 1000000000]
# ]
#
# Q, K = 1, 1
#
# BRR = [
#     [9, 10]
# ]


N = int(input())

ARR = [list(map(int,input().split())) for i in range(N-1)]

Q, K = map(int,input().split())

BRR = [list(map(int,input().split())) for i in range(Q)]


def prepare(n, arr):
    links = {}
    nodeStatus = {}
    distances = {}
    finalDistance = {}
    for i in range(1, N + 1):
        nodeStatus.__setitem__(i, False)
        finalDistance.__setitem__(i, 0)

    for i in range(len(arr)):
        tmp = arr[i]
        startNode = tmp[0]
        endNode = tmp[1]
        distance = tmp[2]
        distances.__setitem__((startNode, endNode), distance)
        distances.__setitem__((endNode, startNode), distance)
        if links.get(startNode) == None:
            links.__setitem__(startNode, [endNode])
        else:
            tmpChild = links.get(startNode)
            tmpChild.append(endNode)
            links.__setitem__(startNode, tmpChild)

        if links.get(endNode) == None:
            links.__setitem__(endNode, [startNode])
        else:
            tmpChild = links.get(endNode)
            tmpChild.append(startNode)
            links.setdefault(endNode, tmpChild)
    return links, nodeStatus, distances, finalDistance


def bfs(startNode):
    q = deque()

    q.append((startNode, 0))

    while len(q):
        currentNode, dist = q.popleft()
        finalDistance.__setitem__(currentNode, dist)
        nodeStatus.__setitem__(currentNode, True)

        childNodes = links.get(currentNode)

        for childNode in childNodes:
            if nodeStatus.get(childNode) == False:
                q.append((childNode, dist + distances.get((currentNode, childNode))))


links, nodeStatus, distances, finalDistance = prepare(N, ARR)

# print(links)
# print(nodeStatus)
# print(distances)
# print(finalDistance)


bfs(K)
for i in range(Q):
    dist1 = finalDistance[BRR[i][0]]
    dist2 = finalDistance[BRR[i][1]]
    print(dist1 + dist2)

N =int(input())
#graph作成
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = list(map(int, input().split()))
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))

Q, K = list(map(int, input().split()))
K -= 1
query = [tuple(int(x) for x in input().split()) for _ in range(Q)]

        
seen = {K} 
v = [K]
distfromK =[0] * N
while len(v) != 0:  #bfsでdistfromKを埋めていく
    for nv in graph[v[0]]:
        if nv[0] in seen:
            continue
        distfromK[nv[0]] = distfromK[v[0]] + nv[1]
        v.append(nv[0])
        seen.add(nv[0])
    v.pop(0)

for q in query:
    print((distfromK[q[0]-1]+distfromK[q[1]-1]))





n = int(input())
G = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, c))
    G[b].append((a, c))

Q, k = tuple(map(int, input().split()))
INF = 10**9*n + 1
dists = [INF] * n
dists[k-1] = 0

from collections import deque
q = deque([k-1])

while q:
    node = q.popleft()
    for to, c in G[node]:
        if dists[to] > dists[node] + c:
            dists[to] = dists[node] + c
            q.append(to)

for _ in range(Q):
    s, g = tuple(map(int, input().split()))
    print(dists[s-1] + dists[g-1])

n = int(input())
G = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    G[a].append((b, c))
    G[b].append((a, c))

Q, k = tuple(map(int, input().split()))
INF = 10**9*n + 1
dists = [INF] * n
dists[k-1] = 0

from collections import deque
q = deque([k-1])
visited = [0] * n
visited[k-1] = 1

while q:
    node = q.popleft()
    for to, c in G[node]:
        if visited[to] == 1:
            continue

        if dists[to] > dists[node] + c:
            dists[to] = dists[node] + c
            q.append(to)

for _ in range(Q):
    s, g = tuple(map(int, input().split()))
    print((dists[s-1] + dists[g-1]))


# 幅優先探索
from collections import deque

N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    links[a].append((b, c))
    links[b].append((a, c))

Q, K = map(int, input().split())

d = [float('inf')] * (N + 1)
d[K] = 0
q = deque([K])
while q:
    i = q.popleft()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
#print('\n'.join(str(v) for v in result))
print(*result, sep='\n')


# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict, namedtuple
import heapq
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline()[:-1] # warning bytes
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
import operator
import random
# string.ascii_lowercase
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1e9)+7
INF = float('inf')

sys.setrecursionlimit(int(1e6))

def solve():
    n = int(input())
    g = defaultdict(list)
    for _ in range(n-1):
        a, b, c = [int(x) for x in input().split()]
        g[a].append((b, c))
        g[b].append((a, c))
    
    q, k = [int(x) for x in input().split()]
    d = defaultdict(int)

    def dfs(v, f, dis):
        d[v] = dis
        for to, xd in g[v]:
            if to == f: continue
            dfs(to, v, dis + xd)
    
    dfs(k, -1, 0)

    for _ in range(q):
        a, b = [int(x) for x in input().split()]
        print((d[a] + d[b]))
    


T = 1
# T = int(input())
for case in range(1,T+1):
    ans = solve()


"""

dp[num_changes][blue_placed]


abba



"""


from collections import deque

N=int(input())
G=[{} for _ in range(N+1)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  G[a][b]=G[b][a]=c
  
def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    cross = []
    todo = deque()
    seen[s]=1
    todo.append(s)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a].keys():
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + G[a][b]
    return d

Q,K=map(int,input().split())
d = bfs(K)
for q in range(Q):
  x,y=map(int,input().split())
  print(d[x]+d[y])

import networkx as nx

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = list(map(int, input().split()))
XY = [list(map(int, input().split())) for _ in range(Q)]

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)

# pred, dist = nx.dijkstra_predecessor_and_distance(G, K - 1)
dist = nx.shortest_path_length(G, K - 1, weight='weight')

for x, y in XY:
    print((dist[x - 1] + dist[y - 1]))



import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]

for i in range(N - 1):
  a,b,c = list(map(int,readline().split()))
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))
  
Q,K = list(map(int,readline().split()))

dist = [0] * N
stack = [(K - 1, -1, 0)]
while stack:
  v,parent,cost = stack.pop()
  dist[v] = cost
  for child, c in G[v]:
    if child == parent:
      continue
    stack.append((child, v, cost + c))
    
for i in range(Q):
  x,y = list(map(int,readline().split()))
  print((dist[x - 1] + dist[y - 1]))


import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
def bfs(place,dis):
  for i in tree[place]:
    a,b=i
    if a not in finish:
      finish.add(a)
      disli[a]=dis+b
      bfs(a,dis+b)
N=INT()
tree=[[] for _ in range(N)]
for i in range(N-1):
  a,b,c=MAP()
  tree[a-1].append([b-1,c])
  tree[b-1].append([a-1,c])
Q,K=MAP()#処理
disli=[0 for i in range(N)]
finish=set([K-1])
bfs(K-1,0)
for i in range(Q):
  a,b=MAP()
  print(disli[a-1]+disli[b-1])

import sys
sys.setrecursionlimit(10**9)

def dfs(now_node,parent_node,dist):
  depth[now_node]=dist
  for next_node,w in graph[now_node]:
    if next_node==parent_node:
      continue
    dfs(next_node,now_node,dist+w)

n=int(input())
graph=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b,c=map(int,input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))
  
q,k=map(int,input().split())
depth=[-1]*(n+1)
dfs(k,0,0)
for _ in range(q):
  x,y=map(int,input().split())
  print(depth[x]+depth[y])


def resolve():
    INF = 1 << 60
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) - 1 for x in input().split()]
        G[a].append((b, c + 1))
        G[b].append((a, c + 1))

    # x -> K, K->y の最短距離,
    # よって K から各地点の最短距離を前計算

    Q, K = list(map(int, input().split()))
    K -= 1

    dist = [INF] * N
    dist[K] = 0
    stack = []
    stack.append(K)
    while stack:
        v = stack.pop()
        for to, c in G[v]:
            if dist[to] <= dist[v] + c:
                continue
            dist[to] = dist[v] + c
            stack.append(to)

    for _ in range(Q):
        x, y = [int(x) - 1 for x in input().split()]
        print((dist[x] + dist[y]))


def __starting_point():
    resolve()

__starting_point()

import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


def bfs(start):
    q = deque([start])
    dist = [-1] * (N + 1)
    dist[start] = 0
    while q:
        v = q.popleft()
        for nv, nw in g[v]:
            if dist[nv] > 0:
                continue
            dist[nv] = dist[v] + nw
            q.append(nv)
    return dist


N = int(input())
g = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    g[a].append((b, c))
    g[b].append((a, c))
Q, K = list(map(int, input().split()))
d = bfs(K)
ans = []
for _ in range(Q):
    x, y = list(map(int, input().split()))
    print((d[x] + d[y]))


import sys
sys.setrecursionlimit(pow(10,6))
readline = sys.stdin.readline

def dfs(nw, d):
    V[nw] = d
    for nx in G[nw]:
        if V[nx[0]]==-1:
            dfs(nx[0], d+nx[1])

n = int(readline())
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(int, readline().split())
    G[a-1].append((b-1,c))
    G[b-1].append((a-1,c))
q, k = map(int, readline().split())

V = [-1]*n
dfs(k-1, 0)

for i in range(q):
    x,y = map(lambda x:int(x)-1, readline().split())
    print(V[x]+V[y])

import sys
sys.setrecursionlimit(10**9)

N = int(input())
G = [[] for _ in range(N)]
length = {}
for _ in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    length[(a-1, b-1)] = c
    length[(b-1, a-1)] = c

r = 0
dist = [0]*N

prv = [None]*N
depth = [0]*N

def dfs(v):
    for u in G[v]:
        if dist[u] > 0 or u ==r: continue
        dist[u] = dist[v] + length[(v, u)]
        depth[u] = depth[v] + 1
        prv[u] = v
        dfs(u)

dfs(r)

# N: 頂点数
# G[v]: 頂点vの子頂点 (親頂点は含まない)
#
# - construct
# prv[u] = v: 頂点uの一つ上の祖先頂点v
# - lca
# kprv[k][u] = v: 頂点uの2^k個上の祖先頂点v
# depth[u]: 頂点uの深さ (根頂点は0)

LV = (N-1).bit_length()
def construct(prv):
    kprv = [prv]
    S = prv
    for k in range(LV):
        T = [0]*N
        for i in range(N):
            if S[i] is None:
                continue
            T[i] = S[S[i]]
        kprv.append(T)
        S = T
    return kprv

def lca(u, v, kprv, depth):
    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LV+1):
        if dd & 1:
            v = kprv[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LV-1, -1, -1):
        pu = kprv[k][u]; pv = kprv[k][v]
        if pu != pv:
            u = pu; v = pv

    # assert kprv[0][u] == kprv[0][v]
    return kprv[0][u]

kprv = construct(prv)

Q, K = map(int, input().split())
K -= 1

ans = []
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    xr = lca(x, K, kprv, depth)
    yr = lca(y, K, kprv, depth)
    a = dist[x] + dist[K] - dist[xr]*2 + dist[y] + dist[K] - dist[yr]*2
    ans.append(a)

print('\n'.join(map(str, ans)))

#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

N = int(input())
adj = [[] for _ in range(N)]
rtree = [None] * N

def dfs(v,parent,dist):
    rtree[v] = dist
    for u, c in adj[v]:
        if u == parent:
            continue
        dfs(u,v,dist+c)

def main():
    for _ in range(N-1):
        a, b, c = list(map(int, input().split()))
        adj[a-1].append((b-1,c))
        adj[b-1].append((a-1,c))
    Q, K = list(map(int, input().split()))

    # Kを頂点とする根付き木を作成する
    dfs(K-1,-1,0)

    for _ in range(Q):
        x, y = [int(x)-1 for x in input().split()]
        print((rtree[x] + rtree[y]))

def __starting_point():
    main()

__starting_point()

import sys

sys.setrecursionlimit(10**6)


N=int(input())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=list(map(int,input().split()))
    G[a-1].append([b-1,c])
    G[b-1].append([a-1,c])

Q,K=list(map(int,input().split()))

SD=[0]*N
def DFS(v,p,d):
    SD[v]=d
    for i,co in G[v]:
        if i==p:continue
        DFS(i,v,d+co)
    return

DFS(K-1,-1,0)

for i in range(Q):
    x,y=list(map(int,input().split()))
    ans=SD[x-1]+SD[y-1]
    print(ans)



from collections import deque
import sys
sys.setrecursionlimit(10**7)
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    a-=1; b-=1
    g[a].append((b, c))
    g[b].append((a, c))
q, k = list(map(int, input().split()))

# 前処理
dist = [-1] * n

def dfs(st, depth=0):
    dist[st] = depth
    for to, c in g[st]:
        if dist[to] >= 0: continue
        dfs(to, depth+c)

dfs(k-1, 0)

for i in range(q):
    x, y = list(map(int, input().split()))
    x-=1; y-=1
    print((dist[x]+dist[y]))



import sys
import queue

n=int(input())

clis=[[] for i in range(n)]

for i in range(n-1):
  ai,bi,ci=map(int,input().split())
  clis[ai-1].append([bi,ci])
  clis[bi-1].append([ai,ci])

q,k=map(int,input().split())

xy=[]

for i in range(q):
  xy.append(list(map(int,input().split())))


distance=[0 for i in range(n)]
seen=[0 for i in range(n)]

que=queue.Queue()

que.put(k)
seen[k-1]=1

while not que.empty():
  c=que.get()
  for aa,cc in clis[c-1]:
    if seen[aa-1]==0:
      distance[aa-1]=distance[c-1]+cc
      seen[aa-1]=1
      que.put(aa)

for i in range(q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

import heapq as hq
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[b].append((a, c))
Q, K = map(int,input().split())
INF = float("inf")
d = [INF]*N
K -= 1
d[K] = 0
q = [(0,K)]
while q:
    dist, i = hq.heappop(q)
    if d[i] < dist:
        continue
    for j, w in edges[i]:
        if d[j] > d[i]+w:
            d[j] = d[i]+w
            hq.heappush(q, (d[j], j))
for _ in range(Q):
    x, y = map(int,input().split())
    x -= 1
    y -= 1
    print(d[x]+d[y])


from heapq import heappush, heappop
def resolve():
    INF = 1 << 60
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) - 1 for x in input().split()]
        G[a].append((b, c + 1))
        G[b].append((a, c + 1))

    # x -> K, K->y の最短距離,
    # よって K から各地点の最短距離を前計算

    Q, K = list(map(int, input().split()))

    K -= 1
    dist = [INF] * N
    hq = []
    heappush(hq, (K, 0))
    dist[K] = 0
    while hq:
        v, cost = heappop(hq)
        for to, c in G[v]:
            if dist[to] <= dist[v] + c:
                continue
            dist[to] = dist[v] + c
            heappush(hq, (to, dist[to]))

    for _ in range(Q):
        x, y = [int(x) - 1 for x in input().split()]
        print((dist[x] + dist[y]))


def __starting_point():
    resolve()

__starting_point()

from collections import defaultdict,deque
n=int(input())
edges=[tuple(map(int,input().split())) for _ in range(n-1)]
q,k=map(int,input().split())
xy=[tuple(map(int,input().split())) for _ in range(q)]

stack=[-1]*(n+1)
stack[k]=0
ed=defaultdict(list)
wt=defaultdict(int)
for e in edges:
  ed[e[0]].append(e[1])
  ed[e[1]].append(e[0])
  wt[(e[0],e[1])]=e[2]
  wt[(e[1],e[0])]=e[2]
ce=deque([(k,x) for x in ed[k]])
ne=deque()
while True:
  while ce:
    e=ce.pop()
    stack[e[1]]=stack[e[0]]+wt[e]
    for v in ed[e[1]]:
      if stack[v]<0:
        ne.append((e[1],v))
  if not ne:
    break
  ce.extend(ne)
  ne.clear()

for que in xy:
  print(stack[que[0]]+stack[que[1]])

N=int(input())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=list(map(int,input().split()))
    G[a-1].append([b-1,c])
    G[b-1].append([a-1,c])

Q,K=list(map(int,input().split()))

SD=[0]*N
seen=[0]*N
stack=[]
stack.append([K-1,0])
seen[K-1]=1
while stack:
    x,d=stack.pop()
    for y,d0 in G[x]:
        if seen[y]==0:
            SD[y]=d+d0
            stack.append([y,d+d0])
            seen[y]=1
for i in range(Q):
    x,y=list(map(int,input().split()))
    ans=SD[x-1]+SD[y-1]
    print(ans)



# 幅優先探索
from collections import deque

N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    links[a].append((b, c))
    links[b].append((a, c))

Q, K = list(map(int, input().split()))

d = [float('inf')] * (N + 1)
d[K] = 0
q = deque([K])
while q:
    i = q.popleft()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = list(map(int, input().split()))
    result.append(d[x] + d[y])
print(('\n'.join(str(v) for v in result)))
#print(*result, sep='\n')


import sys
sys.setrecursionlimit(10**9)
n = int(input())
t = [[] for _ in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  t[a-1].append((b-1,c))
  t[b-1].append((a-1,c))
q,k = map(int,input().split())
k -= 1
l = [0]*n
def dfs(a,b,c):
  for i,j in t[b]:
    if i != a:
      l[i] = c+j
      dfs(b,i,c+j)
dfs(-1,k,0)
for _ in range(q):
  x,y = map(lambda x:int(x)-1,input().split())
  print(l[x]+l[y])

from networkx import *
N = int(input())
E1 = [list(map(int,input().split())) for n in range(N-1)]
Q,K = map(int,input().split())
E2 = [list(map(int,input().split())) for q in range(Q)]
G = Graph()

for a,b,c in E1:
  G.add_edge(a-1,b-1,weight=c)

D = shortest_path_length(G,K-1,weight="weight")

for x,y in E2:
  print(D[x-1]+D[y-1])

import sys
sys.setrecursionlimit(10**9)

n = int(input())
route = [[] for _ in range(n)]
distance = [-1 for _ in range(n)]
INF = float('inf')
    
for _ in range(n-1):
    a, b, c = list(map(int, input().split()))
    route[a-1].append((b-1, c))
    route[b-1].append((a-1, c))
q, k = list(map(int, input().split()))

# 再帰による深さ優先探索
def Tree(s, g, c):
    distance[s] = c
    for g1, val in route[s]:
        if g == g1:
            continue
        Tree(g1, s, c+val)
    
def TransitTreePath():
    Tree(k-1, -1, 0)
    for _ in range(q):
        x, y = list(map(int, input().split()))
        ans = distance[x-1]+distance[y-1]
        print(ans)
        

def __starting_point():
    TransitTreePath()
    

__starting_point()


from collections import defaultdict,deque
import sys
finput=lambda: sys.stdin.readline().strip()

def main():
  n=int(finput())
  edges=[tuple(map(int,finput().split())) for _ in range(n-1)]
  q,k=list(map(int,finput().split()))
  xy=[tuple(map(int,finput().split())) for _ in range(q)]
  
  stack=[-1]*(n+1)
  stack[k]=0
  ed=defaultdict(list)
  wt=defaultdict(int)
  for e in edges:
    ed[e[0]].append(e[1])
    ed[e[1]].append(e[0])
    wt[(e[0],e[1])]=e[2]
    wt[(e[1],e[0])]=e[2]
  ce=deque([(k,x) for x in ed[k]])
  ne=deque()
  while True:
    while ce:
      e=ce.pop()
      stack[e[1]]=stack[e[0]]+wt[e]
      for v in ed[e[1]]:
        if stack[v]<0:
          ne.append((e[1],v))
    if not ne:
      break
    ce.extend(ne)
    ne.clear()
  
  for que in xy:
    print((stack[que[0]]+stack[que[1]]))

def __starting_point():
    main()

__starting_point()

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = MAP()
        adj[a-1].append([b-1, c])
        adj[b-1].append([a-1, c])

    Q, K = MAP()
    K -= 1

    def dijkstra(K, adj):
        #K: 始点, adj[point, cost]:隣接リスト
        d = [inf]*N
        d[K] = 0
        que = []
        heappush(que, K)

        while que:
            v = heappop(que)
            for b, c in adj[v]:
                if d[b] > d[v] + c:
                    d[b] = d[v] + c
                    heappush(que, b)
        return d

    d = dijkstra(K, adj)
    for i in range(Q):
        x, y = MAP()
        print(d[x-1]+d[y-1])

def __starting_point():
    solve()
__starting_point()

N = int(input())

tree = {}

for _ in range(N-1):
  A, B, C = [int(i) for i in input().split()]
  if A not in tree:
    tree[A] = []
  if B not in tree:
    tree[B] = []
  tree[A].append((B, C))
  tree[B].append((A, C))


c = {}
q = []
visited = set()

def dfs(a, acc):
  q.append((a, acc))

  while q:
    n, r = q.pop()
    c[n] = r
    visited.add(n)
    for b, cost in ((b, cost) for b, cost in tree[n] if b not in visited):
      q.append((b, cost + r))


Q, K = [int(i) for i in input().split()]
dfs(K, 0)

for _ in range(Q):
  x, y = [int(i) for i in input().split()]
  print((c[x] + c[y]))


from collections import deque

N = int(input())

graph = [[] for _ in range(N+1)]

for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
    
Q, K = map(int, input().split())

visited = [-1 for _ in range(N+1)]

visited[K] = 0
que = deque()
que.append(K)

while (len(que)):
    now = que.popleft()
    
    for nxt, c in graph[now]:
        if(visited[nxt] != -1):
            continue
        visited[nxt] = visited[now]+c
        que.append(nxt)
        
for i in range(Q):
    x, y = map(int, input().split())
    print(visited[x]+visited[y])

N = int(input())
edges = []
for i in range(N-1):
    a,b,c = map(int,input().split())
    edges.append([a,b,c])

def BFS(K,edges,N):
    roots=[ [] for i in range(N)]
    for a,b,c in edges:
        roots[a-1]+=[(b-1,c)]
        roots[b-1]+=[(a-1,c)]
    dist=[-1]*N
    stack=[]
    stack.append(K)
    dist[K]=0
    while stack:
        label=stack.pop(-1)
        for i,c in roots[label]:
            if dist[i]==-1:
                dist[i]=dist[label]+c
                stack+=[i]
    return dist

Q,K = map(int,input().split())
K = K-1
dist = BFS(K,edges,N)
lsxy = []
for i in range(Q):
    x,y = map(int,input().split())
    x = x-1
    y = y-1
    lsxy.append([x,y])
for i in lsxy:
    print(dist[i[0]]+dist[i[1]])

import sys
sys.setrecursionlimit(10**9)
N=int(input())
T=[[] for _ in range(N)]
for i in range(N-1):
  a,b,c=map(int, input().split())
  T[a-1].append((b-1,c))
  T[b-1].append((a-1,c))
Q,K=map(int, input().split())

dist=[-1]*N
dist[K-1]=0

def dfs(start, nown):
  to=T[start]
  for t in to:
    next_node,c=t
    if dist[next_node]!=-1:
      continue
    nextn=nown+c
    dist[next_node]=nextn
    dfs(next_node, nextn)

dfs(K-1,0)
for i in range(Q):
  x,y=map(int, input().split())
  print(dist[x-1]+dist[y-1])

import sys
sys.setrecursionlimit(10**6)
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
    x,y,z=map(int,input().split())
    edge[x-1].append([y-1,z])
    edge[y-1].append([x-1,z])
q,k=map(int,input().split())
dist=[-1]*n
def dfs(node,d):
    dist[node]=d
    for i in edge[node]:
        if dist[i[0]]==-1:
            dfs(i[0],d+i[1])
dfs(k-1,0)
for i in range(q):
    x,y=map(int,input().split())
    print(dist[x-1]+dist[y-1])

import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
tree = [[] for i in range(N+1)]

for _ in range(N-1):
    a,b,c=list(map(int,input().split()))
    tree[a].append([b,c])
    tree[b].append([a,c])
Q,K=list(map(int,input().split()))
    
memo = [-1]*(N+1)
q = collections.deque([K])
memo[K]=0
while q:
    now = q.pop()
    for direct,cost in tree[now]:
        if memo[direct]== -1:
            memo[direct]=memo[now]+cost
            q.append(direct)
for _ in range(Q):
    a,b=list(map(int,input().split()))
    ans =memo[a]+memo[b]
    print(ans)


import sys
sys.setrecursionlimit(10**7)

n=int(input())

graph = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, w = list(map(int, input().split()))
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))

q,k=list(map(int, input().split()))
k-=1

dist=[-1]*n

def dfs(now, parent, d):
    dist[now]=d
    for i in graph[now]:
        if i[0]==parent:
            continue
        else:
            dfs(i[0], now, d+i[1])

dfs(k, -1, 0)

for _ in range(q):
    x,y=list(map(int, input().split()))
    x-=1
    y-=1
    print((dist[x]+dist[y]))



#!/usr/bin python3
# -*- coding: utf-8 -*-

# ダイクストラ法
# 重み付きグラフ関係により最短経路のリストを作る
# 有向グラフで優先度付きキューで探索

from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')

def dijkstra(s,n,g):
    seen = [False]*n
    cost = [INF]*n
    cost[s] = 0 #スタートはコスト0
    next_q = [(0,s)]
    heapify(next_q)
    while len(next_q)>0:
        c, i = heappop(next_q)
        if cost[i] < c:
            continue
        for nedge, ncost in g[i]:
            nc = cost[i]+ncost
            if cost[nedge]>nc:
                cost[nedge] = nc
                heappush(next_q,(nc, nedge))
    return cost

def main():
    N = int(input())
    graph_F = [[] for _ in range(N)]
#    graph_R = [[] for _ in range(N)]
    #リストの作成
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph_F[a].append((b,c))
        graph_F[b].append((a,c))
#        graph_R[b].append((a,c))

    Q, K = map(int, input().split())
    K -= 1
    F = dijkstra(K,N,graph_F)
    for _ in range(Q):
        x, y = map(int, input().split())
        print(F[x-1]+F[y-1])

def __starting_point():
    main()
__starting_point()

from collections import deque
n=int(input())
e=[[] for _ in range(n+1)]
dist=[-1]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    e[a].append((b,c))
    e[b].append((a,c))
q,k=map(int,input().split())
a=deque()
a.append((k,0))
while a:
    x,d=a.popleft()
    dist[x]=d
    for j,nc in e[x]:
        if dist[j]!=-1:
            continue
        else:
            a.append((j,d+nc))
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    ans.append(dist[x]+dist[y])
print(*ans,sep="\n")

N = int(input())
abclist = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
xylist = [list(map(int, input().split())) for _ in range(Q)]

from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  # graphは隣接リスト(繋がっている先, コスト)
    vsize = len(graph)
    dist = [inf] * vsize
    seen = [False] * vsize
    prev = [None] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  # heapではtuple[0]で比較されるのでこの順番で追加する
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                dist[v] = temp_cost
                prev[v] = u
                heappush(pq, (dist[v], v))
    return dist, prev

graph = [[] for _ in range(N)]
for a, b, c in abclist:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))
shortest_paths, prev = dijkstra(graph, K-1)
for x, y in xylist:
    print(shortest_paths[x-1]+shortest_paths[y-1])


from heapq import heappop,heappush

icase=0
if icase==0:
    n=int(input())
    g=[[] for i in range(n)]
    for i in range(n-1):
        ai,bi,ci=list(map(int,input().split()))
        g[ai-1].append((bi-1,ci))
        g[bi-1].append((ai-1,ci))
if icase==1:
    n=5
    g=[[(1, 1), (2, 1)], [(0, 1), (3, 1)], [(0, 1), (4, 1)], [(1, 1)], [(2, 1)]]
if icase==2:
    n=7
    g=[[(1, 1), (2, 3), (3, 5), (4, 7), (5, 9), (6, 11)], [(0, 1)], [(0, 3)], [(0, 5)], [(0, 7)], [(0, 9)], [(0, 11)]]

q,k=list(map(int,input().split()))
k=k-1

hq=[]
heappush(hq,(0,k)) 

inf=float("INF")
dist=[inf]*n
dist[k]=0
while len(hq)>0:
    dd,state = heappop(hq)
#    print("dd:",dd,"state:",state,"q:",q)
    for v,dv in g[state]:
#        print("v:",v,"dv:",dv,"g[state]:",g[state],"parent[v]:",parent[v])
        if dist[v]>dist[state]+dv:
            dist[v]=dist[state]+dv
            heappush(hq,(dist[v],v))
#            print(" state:",state,"v:",v,"dist[v]",dist[v])

for i in range(q):
    xi,yi=list(map(int,input().split()))
    print((dist[xi-1]+dist[yi-1]))


# 深さ優先探索
N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    links[a].append((b, c))
    links[b].append((a, c))

Q, K = map(int, input().split())

d = [float('inf')] * (N + 1)
d[K] = 0
q = [K]
while q:
    i = q.pop()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
#print('\n'.join(str(v) for v in result))
print(*result, sep='\n')

import networkx as nx

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = list(map(int, input().split()))
XY = [list(map(int, input().split())) for _ in range(Q)]

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)

pred, dist = nx.dijkstra_predecessor_and_distance(G, K - 1)

for x, y in XY:
    print((dist[x - 1] + dist[y - 1]))



N=int(input())
abc=[list(map(int,input().split()))for _ in range(N-1)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split()))for _ in range(Q)]

G=[[]for _ in range(N+1)]
for a,b,c in abc:
    G[a].append([a,b,c])
    G[b].append([b,a,c])

D=[10**9*(N+1)]*(N+1)
D[0]=0
D[K]=0
from collections import*
que=deque(G[K])
while que:
    a,b,c=que.popleft()
    if D[a]+c<D[b]:
        D[b]=D[a]+c
        for g in G[b]:
            que.append(g)

for x,y in xy:
    print(D[x]+D[y])

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
weights = {}

roots = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    roots[a].append(b)
    roots[b].append(a)
    weights[(a,b)] = c
    weights[(b,a)] = c

Q, K = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
    x, y = LI()
    x -= 1
    y -= 1
    xy[i] = [x, y]
"""
xyzで全部の通りを見つけるとN ** 3で無理
なので今回は木構造に注目してBFS or DFSで解いたらいいのでは？
重みを単純にグラフに持つと10**5 ** 2になってしまうので注意
"""

visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0

while len(queue)> 0:
    node = queue.popleft()
    cnt = visited[node]
    for n_node in roots[node]:
        if visited[n_node] == -1:
            visited[n_node] = cnt + weights[(node, n_node)]
            queue.append(n_node)

for x, y in xy:
    print((visited[x] + visited[y]))


# ダイクストラ法
from heapq import heappop, heappush

N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    links[a].append((b, c))
    links[b].append((a, c))

Q, K = map(int, input().split())

d = [float('inf')] * (N + 1)
d[K] = 0
#prev = [None] * (N + 1)
q = [(0, K)]
while q:
    _, u = heappop(q)
    for v, c in links[u]:
        alt = d[u] + c
        if d[v] > alt:
            d[v] = alt
            #prev[v] = u
            heappush(q, (alt, v))

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
print(*result, sep='\n')
#print('\n'.join(str(v) for v in result))


from collections import namedtuple, deque
N = int(input())

connection = [[] for _ in range(N)]
branch = namedtuple('branch',['id', 'dist'])
for _ in range(N-1):
    a, b, c = list(map(int, input().split()))
    connection[a-1].append(branch(b-1, c))
    connection[b-1].append(branch(a-1, c))

dist = [0] * N #dist from root(K)
Q, K = list(map(int, input().split()))
#bfs
reserved = deque([K-1])
seen = {K-1}
while len(reserved) > 0:
    current = reserved.popleft()
    for next in connection[current]:
        if next.id in seen:
            continue
        seen.add(next.id)
        reserved.append(next.id)
        dist[next.id] = dist[current] + next.dist

#deal with query
Query = [list(map(int, input().split())) for _ in range(Q)]
for x,y in Query:
    print((dist[x-1] + dist[y-1]))




import sys
sys.setrecursionlimit(10 ** 9)

n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append([b, c])
    edges[b].append([a, c])
    
q, k = map(int, input().split())

check = [False for _ in range(n)]
dist = [0 for _ in range(n)]
def dfs(pos, b_pos):
    for n_pos, c in edges[pos]:
        if n_pos == b_pos:
            continue
        check[n_pos] = True
        dist[n_pos] = c + dist[pos]
        dfs(n_pos, pos)

check[k - 1] = True
dfs(k - 1, -1)

for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(dist[x] + dist[y])

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n= int(input())
G=[[] for i in range(n+1)]

for i in range(n-1):
	a,b,c=map(int, input().split())
	G[a].append([b,c])
	G[b].append([a,c])

q,k=map(int,input().split())


D=[None]*(n+1)
 
def dfs(x,d):
    D[x]=d
    for yy,dd in G[x] :
        if D[yy] is not None:
            continue
        dfs(yy,dd+d)
dfs(k,0)

for i in range(q):
    x, y = map(int, input().split())
    print(D[x] + D[y])

# 深さ優先探索
N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    links[a].append((b, c))
    links[b].append((a, c))

Q, K = map(int, input().split())

d = [float('inf')] * (N + 1)
d[K] = 0
q = [K]
while q:
    i = q.pop()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = map(int, input().split())
    result.append(d[x] + d[y])
#print('\n'.join(str(v) for v in result))
print(*result, sep='\n')


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


def dijkstra(s, n): # (始点, ノード数)
    dist = [inf] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        seen[v] = True
        for to, cost in adj[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

N = ni()
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = na()
    adj[a-1].append((b-1, c))
    adj[b-1].append((a-1, c))

Q, K = na()
ans = []
d = dijkstra(K-1, N)

for i in range(Q):
    x, y = na()
    x -= 1
    y -= 1
    ans.append(d[x] + d[y])

for i in range(Q):
    print((ans[i]))



import sys
sys.setrecursionlimit(10**9)

n = int(input())

tree = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    tree[a].append((b,c))
    tree[b].append((a,c))

q,k = map(int,input().split())

distance = [-1 for i in range(n+1)]

#再帰でkから各頂点までの距離を求める
def dfs(now, pre, c):
    distance[now] = c
    for nxt, val in tree[now]:
        if nxt == pre:
            continue
        dfs(nxt, now, c+val)

dfs(k, -1, 0)

for i in range(q):
    x,y = map(int,input().split())
    print(distance[x] + distance[y])

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)] 
    for _ in range(N - 1):
        a, b, c = LI()
        G[a-1].append((b - 1, c))
        G[b-1].append((a - 1, c))
    Q, K = LI()
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    que = collections.deque()
    que.append(K)
    while que:
        c = que.popleft()
        for n, l in G[c]:
            if dist[n] == -1:
                dist[n] = dist[c] + l
                que.append(n)

    for _ in range(Q):
        x, y = LI_()
        ans = dist[x] + dist[y]
        print(ans)

def __starting_point():
    resolve()

__starting_point()

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

N = k()
edge = [[] for _ in range(N+1)]

for _ in range(N-1):
    a,b,c = I()
    edge[a].append((b,c))
    edge[b].append((a,c))

Q,K = I()

dist = [None]*(N+1)

def dfs(x,d):
    dist[x] = d
    for y,dd in edge[x]:
        if dist[y] is not None:
            continue
        dfs(y,d+dd)

dfs(K,0)
for _ in range(Q):
    x,y = I()
    print(dist[x]+dist[y])

import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b, c = map(int, readline().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))

    Q, K, *XY = map(int, read().split())
    K -= 1

    hq = [(0, K)]
    dist = [INF] * N
    dist[K] = 0
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for nv, cost in G[v]:
            if dist[nv] > d + cost:
                dist[nv] = d + cost
                heappush(hq, (dist[nv], nv))

    ans = [0] * Q
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        ans[i] = dist[x - 1] + dist[y - 1]

    print(*ans, sep='\n')
    return


def __starting_point():
    main()

__starting_point()

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
adj = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))

Q, K = list(map(int, input().split()))
K -= 1

def dijkstra(start):
    dist = [INF for _ in range(N)]
    visited = [False for _ in range(N)] 
    q = [(0, start)]
    dist[start] = 0
    while len(q) > 0:
        v = heapq.heappop(q)
        a = v[1]
        if visited[a]:
            continue
        visited[a] = True
        for u in adj[a]:
            w = u[0]
            b = u[1]
            if dist[a] + w < dist[b]: 
                dist[b] = dist[a] + w
                heapq.heappush(q, (dist[b], b))
    return dist

dist = dijkstra(K)

for i in range(Q):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1
    print((dist[x] + dist[y]))


import sys
sys.setrecursionlimit(1000000)
N = int(input())
tree = [[] for i in range(N)]

for i in range(N-1):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  tree[a].append([b, c])
  tree[b].append([a, c])

Q, K = map(int, input().split())
K -= 1
dis = [0]*N

def main(v, p, d):
  dis[v] = d
  for x, y in tree[v]:
    if x == p:
      continue
    main(x, v, d+y)
    
main(K, -1, 0)

for i in range(Q):
  x, y = map(int, input().split())
  ans = dis[x-1] + dis[y-1]
  print(ans)

import sys
sys.setrecursionlimit(20000000)
# N = 5
# ARR = [
#     [1, 2, 1],
#     [1, 3, 1],
#     [2, 4, 1],
#     [3, 5, 1]
# ]
#
# Q, K = 3, 1
#
# BRR = [
#     [2, 4],
#     [2, 3],
#     [4, 5],
# ]
#
#

N = int(input())

ARR = [list(map(int,input().split())) for i in range(N-1)]

Q, K = map(int,input().split())

BRR = [list(map(int,input().split())) for i in range(Q)]



def prepare(arr, n):
    links = [[] for i in range(n)]
    depth = [0 for i in range(n)]
    for i in range(n - 1):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1
        dist = arr[i][2]

        links[startNode].append((endNode, dist))
        links[endNode].append((startNode, dist))

    return links, depth


def dfs(currentNode, parrentNode=-1, dist=0):
    childNodes = links[currentNode]
    depths[currentNode] = dist
    for (childNode, childDistance) in childNodes:
        if childNode == parrentNode:
            continue

        dfs(childNode, currentNode, dist + childDistance)


links, depths = prepare(ARR, N)

dfs(K - 1)

for i in range(Q):
    p1 = BRR[i][0] - 1
    p2 = BRR[i][1] - 1

    d1 = depths[p1]
    d2 = depths[p2]

    print(d1 + d2)

import heapq
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append([c, b - 1])
    G[b - 1].append([c, a - 1])
Q, K = map(int, input().split())

def dijkstra(s, N, G):
    d = [float('inf')] * N
    d[s] = 0
    hq = [[0, s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        v, i = heapq.heappop(hq)
        if d[i] < v:
            continue
        for c, j in G[i]:
            if d[j] > d[i] + c:
                d[j] = d[i] + c
                heapq.heappush(hq, [d[j], j])
    return d

D = dijkstra(K - 1, N, G)

dist = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    dist[i] = D[x - 1] + D[y - 1]

for d in dist:
    print(d)

import sys
sys.setrecursionlimit(10**9)

N = int(input())

graph = [[] for _ in range(N)]

for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))
    
Q, K = map(int, input().split())
visited = [0 for _ in range(N)]

def DFS(a, b, c):
    for i, j in graph[b]:
        if(i != a):
            visited[i] = c+j
            DFS(b, i, c+j)
DFS(-1, K-1, 0)
             
for _ in range(Q):
    x, y = map(int, input().split())
    print(visited[x-1]+visited[y-1])

#グラフの連結成分を調べる
def Graph(ab):
    G = [[] for i in range(n)]
    for a, b, c in ab:
        G[a - 1].append([b, c])
        G[b - 1].append([a, c])
    return G

from collections import deque
def bfs(k):
    q = deque()
    q.append((k, - 1, 0))
    dis = [0] * n 
    while q:
        V, P, cnt = q.popleft()
        for nv, d in G[V - 1]:
            if nv == P:continue
            dis[nv - 1] = cnt + d
            q.append((nv, V, cnt + d))
    
    return dis 

n = int(input())
abc = [list(map(int,input().split())) for _ in range(n - 1)]
G = Graph(abc)
q, k = map(int,input().split())
dis = bfs(k)

for _ in range(q):
    x, y = map(int,input().split())
    print(dis[x - 1] + dis[y - 1])

from networkx import *
N = int(input())
E1 = [list(map(int,input().split())) for n in range(N-1)]
Q,K = map(int,input().split())
E2 = [list(map(int,input().split())) for q in range(Q)]
G = Graph()

for a,b,c in E1:
  G.add_edge(a-1,b-1,weight=c)

D = shortest_path_length(G,weight="weight",target=K-1)

for x,y in E2:
  print(D[x-1]+D[y-1])

N=int(input())
G=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=list(map(int,input().split()))
    a-=1
    b-=1
    G[a].append([b,c])
    G[b].append([a,c])
Q,K=list(map(int,input().split()))
K-=1
dist=[-1 for _ in range(N)]
dist[K]=0
q=[K]
while len(q)>0:
    v=q.pop()
    for p in G[v]:
        nv=p[0]
        if dist[nv]!=-1:
            continue
        dist[nv]=dist[v]+p[1]
        q.append(nv)
for _ in range(Q):
    x,y=list(map(int,input().split()))
    print((dist[x-1]+dist[y-1]))


import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
from heapq import heappop, heappush
def main():
        

    def dijkstra(k):
        def push(v, x):
            if dist[v] <= x:
                return
            dist[v] = x
            heappush(q, (x, v))

        inf = 10**18
        dist = [inf]*n
        q = []
        push(k, 0)
        while q:
            x, v = heappop(q)
            if x > dist[v]:
                continue
            for nv, c in g[v]:
                push(nv, x+c)
        return dist

    n = ii()
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b, c = mi()
        a -= 1
        b -= 1

        g[a].append((b, c))
        g[b].append((a, c))
    q, k = mi()
    k -= 1
    dist = dijkstra(k)
    for i in range(q):
        a, b = mi()
        a -= 1
        b -= 1
        print(dist[a]+dist[b])


def __starting_point():
    main()
__starting_point()

import networkx as nx

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = list(map(int, input().split()))
XY = [list(map(int, input().split())) for _ in range(Q)]

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)

# pred, dist = nx.dijkstra_predecessor_and_distance(G, K - 1)
dist = nx.shortest_path_length(G, K - 1, weight="weight", method="bellman-ford")

for x, y in XY:
    print((dist[x - 1] + dist[y - 1]))



from networkx import *
N = int(input())
E1 = [list(map(int,input().split())) for n in range(N-1)]
Q,K = map(int,input().split())
E2 = [list(map(int,input().split())) for q in range(Q)]
G = Graph()

for a,b,c in E1:
  G.add_edge(a-1,b-1,weight=c)

D = shortest_path_length(G,target=K-1,weight="weight")

for x,y in E2:
  print(D[x-1]+D[y-1])

import sys

def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack.append(i)
  return dist
      
      
a = []
edge = []
for l in sys.stdin:
    a.append(l.split())
V = int(a[0][0])
for i in range(V-1):
  buf = [int(a[i+1][0])-1, int(a[i+1][1])-1, int(a[i+1][2])]
  edge.append(buf)
n = int(a[V][0])
s = int(a[V][1])-1
ques = []
for i in range(n):
  buf = [int(a[V+i+1][0])-1, int(a[V+i+1][1])-1]
  ques.append(buf)
dist = BFS(s, edge, V)
for a, b in ques:
  res = dist[a] + dist[b]
  print(res)

import sys
import heapq

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: list(map(int, readline().split()))
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: list(map(int, read().split()))
in_s = lambda: readline().rstrip().decode('utf-8')


INF = 10**18


def dijkstra(N, s0, edge):

    d = [INF] * N  # 始点からの距離
    used = [False] * N  # 探索済みリスト
    edgelist = [(0, s0)]  # 始点はコスト0で初期化
    heapq.heapify(edgelist)  # ヒープにpush

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d


def main():
    N = in_n()

    edge = [[]for _ in range(N)]
    for i in range(N - 1):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    Q, K = in_nn()
    d = dijkstra(N, K - 1, edge)

    ans = []
    for i in range(Q):
        x, y = in_nn()
        x, y = x - 1, y - 1
        ans.append(d[x] + d[y])

    print(('\n'.join(map(str, ans))))


def __starting_point():
    main()

__starting_point()

import heapq
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))

q, k = map(int, input().split())
ds = [-1]*n
hq = [(0,k-1)]
while hq:
    c,idx = heapq.heappop(hq)
    if ds[idx] != -1:
        continue
    ds[idx] = c
    for i in g[idx]:
        if ds[i[0]] == -1:
            heapq.heappush(hq,(i[1]+c,i[0]))

for i in range(q):
    x, y = map(int, input().split())
    print(ds[x-1]+ds[y-1])

import collections

n = int(input())
route = {i + 1 : {} for i in range(n)}
for i in range(n - 1):
    a, b, c = map(int, input().split())
    route[a][b] = c
    route[b][a] = c
q, k = map(int, input().split())
queue = collections.deque([k])
length = [0] * (n + 1)
while queue:
    search = queue.popleft()
    pairs = []
    for i, j in route[search].items():
        queue.append(i)
        length[i] = length[search] + j
        pairs.append([search, i])
    for i, j in pairs:
        del route[i][j]
        del route[j][i]
for i in range(q):
    x, y = map(int, input().split())
    print(length[x] + length[y])

def main():
    N = int(input())
    adj = [[] for _ in range(N)]
    node = [0] * N
    for _ in range(N-1):
        a, b, c = list(map(int, input().split()))
        adj[a-1].append((b-1, c))
        adj[b-1].append((a-1, c))
    
    Q, K = list(map(int, input().split()))
    K -= 1

    # import
    from collections import deque

    que = deque([K])
    check = set([K])
    for _ in range(N*2):
        u = que.popleft()
        for v, c in adj[u]:
            if v in check:
                continue
            node[v] = node[u] + c
            que.append(v)
            check.add(v)
        if len(que) == 0:
            break
    
    for _ in range(Q):
        x, y = list(map(int, input().split()))
        ans = node[x-1] + node[y-1]
        print(ans)

def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10**7)

N = int(input())
tree = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = list(map(int, input().split()))
    tree[a-1].append([b-1, c])
    tree[b-1].append([a-1, c])
Q, K = list(map(int, input().split()))

dist = [-1] * N
def dfs(v, total_cost):
    # v：頂点, total_cost：今までかかったコストの合計
    dist[v] = total_cost
    for v_next, cost in tree[v]:
        if dist[v_next] >= 0:
            continue
            # v_nextが訪問済みならスキップ
        dfs(v_next, total_cost+cost)

dfs(K-1, 0)

for i in range(Q):
    x, y = list(map(int, input().split()))
    print((dist[x-1] + dist[y-1]))


from collections import deque
n=int(input())
num=[[] for _ in range(n)]
for i in range(n-1):
    a,b,c=list(map(int,input().split()))
    num[a-1].append([b,c])
    num[b-1].append([a,c])
q,k=list(map(int,input().split()))
seen=[False]*n
queue=deque()
queue.append(k)
ans=[0]*n
seen[k-1]=True
for i in range(n):
    if len(queue)==0:
        break
    num1=queue.popleft()
    for j in range(len(num[num1-1])):
        num2=num[num1-1][j][0]
        if seen[num2-1]==False:
            queue.append(num2)
            seen[num2-1]=True
            ans[num2-1]=ans[num1-1]+num[num1-1][j][1]
for i in range(q):
    x,y=list(map(int,input().split()))
    print((ans[x-1]+ans[y-1]))


#!/usr/bin/env python
# coding: utf-8

# In[1]:


from collections import deque


# In[6]:


N = int(input())
t = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,c = list(map(int, input().split()))
    t[a-1].append([b,c])
    t[b-1].append([a,c])


# In[7]:


Q,K = list(map(int, input().split()))


# In[8]:


visited = [-1 for _ in range(N)]
visited[K-1] = 0
que = deque()
que.append(K)
while len(que):
    now = que.popleft()
    for nxt,c in t[now-1]:
        if visited[nxt-1] != -1:
            continue
        visited[nxt-1] = visited[now-1]+c
        que.append(nxt)
for i in range(Q):
    x,y = list(map(int, input().split()))
    print((visited[x-1]+visited[y-1]))


# In[ ]:






from collections import deque

N = int(input())
abc = [list(map(int, input().split())) for _ in range(N-1)]
q, K = map(int, input().split())

graph = [[] for i in range(N+1)]
for i,j,k in abc:
    graph[i].append((j,k))
    graph[j].append((i,k))
    
r = [-1 for i in range(N+1)] 
Q = deque()
Q.append(K)
r[K] = 0

while Q:
    x = Q.popleft()
    for to, dis in graph[x]:
        if r[to] == -1:
            r[to] = r[x] + dis
            Q.append(to)
            
for _ in range(q):
    x, y = map(int, input().split())
    print(r[x] + r[y])

from collections import deque

n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append([b, c])
    e[b].append([a, c])

m, k = map(int,input().split())
k -= 1

d = [-1] * n
d[k] = 0
q = deque()
q.append([k, 0])
while q:
    f, cc = q.pop()
    for t, nc in e[f]:
        if d[t] == -1:
            d[t] = cc + nc
            q.append([t, d[t]])

for i in range(m):
    f, t = map(int,input().split())
    f -= 1
    t -= 1
    print(d[f] + d[t])

N=int(input())
links=[[] for _ in range(N+1)]
for _ in range(N-1):
  a, b, c=map(int, input().split())
  links[a].append([b, c])
  links[b].append([a, c])
  
Q, K=map(int, input().split())

length=[-1]*(N+1)
length[K]=0

import heapq
q=[[tmp[1], tmp[0], K] for tmp in links[K]]
heapq.heapify(q)
while q:
  tmp=heapq.heappop(q)
  length[tmp[1]]=tmp[0]+0
  for x in links[tmp[1]]:
    if tmp[2]!=x[0]:
      heapq.heappush(q, [tmp[0]+x[1], x[0], tmp[1]])

for _ in range(Q):
  x, y=map(int, input().split())
  print(length[x]+length[y])

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7
def intread():
    return int(sysread())
def mapline(t = int):
    return list(map(t, sysread().split()))
def mapread(t = int):
    return list(map(t, read().split()))

def dfs(current, to, dists):
    c, c_cost = current
    dists[c] = c_cost
    for n, n_cost in to[c]:
        if dists[n] == -1:
            dfs((n, c_cost + n_cost), to, dists)
    return dists


def run():
    N = intread()
    to = [[] for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = mapline()
        to[a].append((b, c))
        to[b].append((a, c))
    Q, K = mapline()

    dists = [-1] * (N+1)
    dists = dfs((K, 0), to, dists)
    for i in range(Q):
        x,y= mapline()
        print((dists[x] + dists[y]))

def __starting_point():
    run()

__starting_point()

import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b, c = map(int, readline().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))

    Q, K, *XY = map(int, read().split())
    K -= 1

    stack = deque([K])
    dist = [INF] * N
    dist[K] = 0
    while stack:
        v = stack.pop()
        for nv, cost in G[v]:
            if dist[nv] == INF:
                dist[nv] = dist[v] + cost
                stack.append(nv)

    ans = [0] * Q
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        ans[i] = dist[x - 1] + dist[y - 1]

    print(*ans, sep='\n')
    return


def __starting_point():
    main()

__starting_point()

def main():
    n = int(input())
    G = {}
    for i in range(n):
        G[i+1] = []
    for _ in range(n-1):
        a,b,c = list(map(int,input().split()))
        G[a] += [[b,c]]
        G[b] += [[a,c]]
    q,k = list(map(int,input().split()))
    dist = [-1]*n
    dist[k-1] = 0
    que = [k]
    while len(que) > 0:
        s = que.pop(0)
        for [nv,c] in G[s]:
            if dist[nv-1] != -1:
                continue
            dist[nv-1] = dist[s-1]+c
            que.append(nv)
    for _ in range(q):
        x,y = list(map(int,input().split()))
        print((dist[x-1]+dist[y-1]))

def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10 ** 6)
N=int(input())
l=[-1]*N
tree=[[] for i in range(N)]
for i in range(N-1):
   A,B,C=list(map(int,input().split()))
   A-=1;B-=1
   tree[A].append((B,C))
   tree[B].append((A,C))
Q,V=list(map(int,input().split()))
def DFS(now,past,dis):
   l[now]=dis
   for i in tree[now]:
      if i[0]==past:
         continue
      elif l[i[0]] == -1:
         DFS(i[0],now,dis+i[1])
DFS(V-1,-1,0)
for i in range(Q):
   s,e=list(map(int,input().split()))
   s-=1;e-=1
   print(l[s]+l[e])

import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
d = [-1 for i in range(n)]
e = [[] for i in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    e[a - 1].append([b - 1, c])
    e[b - 1].append([a - 1, c])
q, k = map(int, input().split())
def dfs(cur, par, di):
    d[cur] = di
    for i in e[cur]:
        if d[i[0]] == -1:
            if i == par:
                continue
            dfs(i[0], cur, di + i[1])
dfs(k - 1, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    print(d[x - 1] + d[y - 1])

# ダイクストラ法
from heapq import heappop, heappush

N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    links[a].append((b, c))
    links[b].append((a, c))

Q, K = list(map(int, input().split()))

d = [float('inf')] * (N + 1)
d[K] = 0
#prev = [None] * (N + 1)
q = [(0, K)]
while q:
    _, u = heappop(q)
    for v, c in links[u]:
        alt = d[u] + c
        if d[v] > alt:
            d[v] = alt
            #prev[v] = u
            heappush(q, (alt, v))

result = []
for _ in range(Q):
    x, y = list(map(int, input().split()))
    result.append(d[x] + d[y])
#print(*result, sep='\n')
print(('\n'.join(str(v) for v in result)))


import sys  
sys.setrecursionlimit(200000)

N = int(input())
adj = {}

adj = {i+1: [] for i in range(N)}

for i in range(N-1):
    a, b, c = map(int, input().split())

    adj[a].append((b, c))
    adj[b].append((a, c))

dis = [0] * N

def dfs(k, u, d):
    """
    u: kの親
    d: vとuの最短距離
    adj_v: vの隣接
    これらのじょうけんのもとでdisを更新する
    """
    dis[k-1] = d

    for p, pk_dis in adj[k]:
        if p != u:
            dfs(p, k, d+pk_dis)

Q, K = map(int, input().split())
dfs(K, -1, 0)

for i in range(Q):
  x, y = map(int, input().split())
  print(dis[x-1] + dis[y-1])