Problem:
 Score : 400 points    Problem Statement 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 1 5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5      Sample Output 1 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         Sample Input 2 7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7      Sample Output 2 5
14
22  The path for each query must pass Vertex K=2 .       Sample Input 3 10
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
1 1
9 10      Sample Output 3 17000000000

Solution (Python):
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

d=defaultdict(list)
n=int(input())

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


def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

q,k=map(int,input().split())
y=DIJKSTRA(k,d)

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

Solution (Python):
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

d=defaultdict(list)
n=int(input())

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


def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

q,k=map(int,input().split())
y=DIJKSTRA(k,d)

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

Solution (Python):
import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[[] for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1].append([b-1,c])
    path[b-1].append([a-1,c])
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in path[cur]:
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])

Solution (Python):
import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[deque() for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1].append([b-1,c])
    path[b-1].append([a-1,c])
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in path[cur]:
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])

Solution (Python):
import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[deque() for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1].append([b-1,c])
    path[b-1].append([a-1,c])
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in path[cur]:
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])

Solution (Python):
import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[[] for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1].append([b-1,c])
    path[b-1].append([a-1,c])
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in path[cur]:
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])

Solution (Python):
N = int( input() )


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

dist = [0]*N
q = [K-1]
while q:
    tmp = q.pop()
    for v in V[tmp]:
        if dist[v[0]] == 0:
            dist[v[0]] = dist[tmp] + v[1]
            q.append( v[0] )

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n = int(input())
abc = [[int(item) for item in input().split()] for _ in range(n-1)]
q, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(q)]

distance = [0] * n
e = [[] for _ in range(n)]
w = [[] for _ in range(n)]
for a, b, c in abc:
    e[a-1].append(b-1)
    e[b-1].append(a-1)
    w[a-1].append(c)
    w[b-1].append(c)

def dfs(v, par, dist):
    distance[v] = dist
    if len(e[v]) == 0:
        return True
    for i in range(len(e[v])):
        if e[v][i] == par:
            continue
        dfs(e[v][i], v, dist + w[v][i])

dfs(k-1, -1, 0)
for x, y in xy:
    print(distance[x-1] + distance[y-1])

Solution (Python):
import heapq

N = int(input())
d = [0] * N
INF = float('inf')

class Info:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append(Info(b - 1, c))
    G[b - 1].append(Info(a - 1, c))
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                heapq.heappush(h, [d[e.to], e.to])

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

dijkstra(K - 1)

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

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    heap = [(0,start)]
    
    
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

n = ni()

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

for _ in range(n-1):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c, b))
    graph[b].append((c, a))

q,k = li()
k -= 1

query = []
for _ in range(q):
    x, y = li_()
    query.append((x, y))
    
dist = dijkstra(graph, n, k)
    
for qx, qy in query:
    print(dist[qx] + dist[qy])

Solution (Python):
from collections import deque

def main():
    n=int(input())
    l=[0]*n
    d={}
    for i in range(n-1):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        if a in d:
            d[a].add((b,c))
        else:
            d[a]={(b,c)}
        if b in d:
            d[b].add((a,c))
        else:
            d[b]={(a,c)}
    q,k=map(int,input().split())
    k-=1
    p=deque([k])
    while len(p):
        w=p.popleft()
        for i in d[w]:
            if (l[i[0]]==0 and i[0]!=k) or (l[i[0]]!=0 and l[i[0]]>l[w]+i[1]):
                l[i[0]]=l[w]+i[1]
                p.append(i[0])

    for i in range(q):
        x,y=map(int,input().split())
        print(l[x-1]+l[y-1])
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    n=int(input())
    l=[0]*n
    d={}
    for i in range(n-1):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        if a in d:
            d[a].add((b,c))
        else:
            d[a]={(b,c)}
        if b in d:
            d[b].add((a,c))
        else:
            d[b]={(a,c)}
    q,k=map(int,input().split())
    k-=1
    p=deque([k])
    while len(p):
        w=p.popleft()
        for i in d[w]:
            if (l[i[0]]==0 and i[0]!=k) or (l[i[0]]!=0 and l[i[0]]>l[w]+i[1]):
                l[i[0]]=l[w]+i[1]
                p.append(i[0])

    for i in range(q):
        x,y=map(int,input().split())
        print(l[x-1]+l[y-1])
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n=int(input())
l=[0]*n
d={}
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    if a in d:
        d[a].add((b,c))
    else:
        d[a]={(b,c)}
    if b in d:
        d[b].add((a,c))
    else:
        d[b]={(a,c)}
q,k=map(int,input().split())
k-=1
p=deque([k])
while len(p):
    w=p.popleft()
    for i in d[w]:
        if (l[i[0]]==0 and i[0]!=k) or (l[i[0]]!=0 and l[i[0]]>l[w]+i[1]):
            l[i[0]]=l[w]+i[1]
            p.append(i[0])

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

Solution (Python):
from collections import deque
n=int(input())
l=[0]*n
d={}
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    if a in d:
        d[a].add((b,c))
    else:
        d[a]={(b,c)}
    if b in d:
        d[b].add((a,c))
    else:
        d[b]={(a,c)}
q,k=map(int,input().split())
k-=1
p=deque([k])
while len(p):
    w=p.popleft()
    for i in d[w]:
        if (l[i[0]]==0 and i[0]!=k) or (l[i[0]]!=0 and l[i[0]]>l[w]+i[1]):
            l[i[0]]=l[w]+i[1]
            p.append(i[0])

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

Solution (Python):
import sys
from collections import deque

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

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

    k_dist = [0 for _ in range(N)]
    start = deque()
    start.append(K)
    while len(start) > 0:
        s = start.popleft()
        for dest, cost in d[s]:
            if k_dist[dest] > 0:
                continue

            k_dist[dest] = k_dist[s] + cost
            start.append(dest)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

def dfs(start, dest, pre, d):
    if d[start][dest] > 0:
        return d[start][dest]

    for i in range(len(d)):
        if d[start][i] > 0 and i != pre:
            c = dfs(i, dest, start, d)
            if c > 0:
                return d[start][i] + dfs(i, dest, start, d)

    return 0

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

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

    k_dist = [0 for _ in range(N)]
    start = deque()
    start.append(K)
    while len(start) > 0:
        s = start.popleft()
        for dest, cost in d[s]:
            if k_dist[dest] > 0:
                continue

            k_dist[dest] = k_dist[s] + cost
            start.append(dest)

    for _ in range(Q):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1

        print(int(k_dist[x] + k_dist[y]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
n=int(input())
s=[[]for i in range(n+1)]
g=[0]*(n+1)
h=[True]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    s[a].append([b,c])
    s[b].append([a,c])
def dfs(x):
    h[x]=False
    for i in s[x]:
        if h[i[0]]:
            g[i[0]]=g[x]+i[1]
            dfs(i[0])
q,k=map(int,input().split())
dfs(k)
for i in range(q):
    x,y=map(int,input().split())
    print(g[x]+g[y])

Solution (Python):
from queue import Queue


def distances(tree: list, treeSize: int, root: int)->list:
    dists = [0] * treeSize

    q = Queue()
    q.put((root, -1, 0))

    while not q.empty():
        v, prev, d2v = q.get()

        dists[v] = d2v
        for u, dv2u in tree[v]:
            if prev == u:
                continue
            q.put((u, v, d2v + dv2u))

    return dists


def transit_tree_path(
        N: int, edges: list, Q: int, K: int, queries: list)->list:
    tree = [[] for _ in range(N)]
    for u, v, c in edges:
        tree[u-1].append((v-1, c))
        tree[v-1].append((u-1, c))

    d = distances(tree, N, K-1)

    return [d[x-1]+d[y-1] for x, y in queries]


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(N-1)]
    Q = 0
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = transit_tree_path(N, edges, Q, K, queries)
    for a in ans:
        print(a)

Solution (Python):
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
    branch[b]|={(a,c),}
Q,K=map(int,input().split())
dist=[float('inf')]*(N+1)
dist[K]=0
check=deque([K])
while len(check)>0:
    now=check.popleft()
    for nex,c in branch[now]:
        if dist[nex]>dist[now]+c:
            dist[nex]=dist[now]+c
            check.append(nex)
for q in range(Q):
    x,y=map(int,input().split())
    print(dist[x]+dist[y])

Solution (Python):
from collections import deque
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

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



def solve(G,K,P):
    q=deque()
    q.append(K)
    while q:
        s=q.pop()
        for i in G[s]:
            if(P[i.to]):
                continue
            P[i.to]=True
            A[i.to]=A[s]+i.cost
            q.append(i.to)

Q,K=map(int,input().split())
A[K-1]=0
P[K-1]=True
solve(G,K-1,P)


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

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

INF = 10**9 * N
distance = [INF for _ in range(N+1)]
distance[K] = 0
settled = set()
h = [(0,K)]
while len(h) > 0:
    d,v = heapq.heappop(h)
    if v in settled:
        continue
    settled.add(v)
    distance[v] = d
    for (w,a) in edges[v]:
        if distance[v] + a < distance[w]:
            distance[w] = distance[v] + a
            heapq.heappush(h,(distance[w],w))

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
inf = float("inf")
road = [dict() for _ in range(n+1)]
for _ in range(n-1):
  a,b,c = map(int, input().split())
  road[a][b] = c
  road[b][a] = c
q,k = map(int, input().split())
dfs = [inf]*(n+1)
dfs[k] = 0
def dodfs(x):
  for i in road[x]:
    if dfs[i] == inf:
      dfs[i] = dfs[x] + road[x][i]
      dodfs(i)
  return   
dodfs(k)
for _ in range(q):
  x,y = map(int, input().split())
  print(dfs[x] + dfs[y])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

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

Q,K = map(int,input().split())
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]
dis = [0]*N

def dfs(v=K,d=0,pv=-1):
    for nv,nd in ad[v]:
        if nv == pv:
            continue
        dis[nv] = d+nd
        dfs(nv,d+nd,v)

dfs()
for x,y in query:
    ans = dis[x] + dis[y]
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

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

Q,K = map(int,input().split())
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]
dis = [0]*N

def bfs(sv=K):
    dq = deque()
    dq.append((sv,0,-1))
    while dq:
        v,d,pv = dq.pop()
        for nv,nd in ad[v]:
            if nv == pv:
                continue
            dis[nv] = d+nd
            dq.append((nv,d+nd,v))

bfs()
for x,y in query:
    ans = dis[x] + dis[y]
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

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

Q,K = map(int,input().split())
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]
dis = [0]*N

def bfs(sv=K):
    dq = deque()
    dq.append((sv,0,-1))
    while dq:
        v,d,pv = dq.popleft()
        for nv,nd in ad[v]:
            if nv == pv:
                continue
            dis[nv] = d+nd
            dq.append((nv,d+nd,v))

bfs()
for x,y in query:
    ans = dis[x] + dis[y]
    print(ans)

Solution (Python):
import heapq


class Dijkstra:
    """ダイクストラ法を行う.0-index"""

    def __init__(self, graph, start_point, goal_point=None):
        """Intialization.

        :param graph:List[Dict[int, int]]
        :param start_point: start index
        :param goal_point: goal index
        """
        node_num = len(graph)
        self.graph = graph
        self.start_point = start_point
        self.goal_point = goal_point
        self.dist = [float("inf") for _ in range(node_num)]
        self.prev = [float("inf") for _ in range(node_num)]

    def run(self):
        self.dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            
            prev_cost, src = heapq.heappop(heap_q)

            if self.dist[src] < prev_cost:
                continue

            for dest, cost in self.graph[src].items():
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    
                    heapq.heappush(heap_q, (self.dist[dest], dest))
                    self.prev[dest] = src
        if self.goal_point is not None:
            return self.get_path()
        else:
            return self.dist

    def get_path(self):
        path = [self.goal]
        dest = self.goal

        while self.prev[dest] != float("inf"):
            path.append(self.prev[dest])
            dest = self.prev[dest]

        return list(reversed(path))


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

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

solver = Dijkstra(graph, K - 1)
d = solver.run()

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

Solution (Python):
from collections import deque

INF = float("inf")


def main():
    N = int(input())
    E = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        E[a] += [(b, c)]
        E[b] += [(a, c)]
    path = [INF] * (N+1)
    Q, K = map(int, input().split())
    q = deque([(K, 0)])
    while len(q):
        x, cost = q.popleft()
        path[x] = cost
        for e in E[x]:
            nx, nc = e
            if path[nx] == INF:
                q.append((nx, cost+nc))
    for _ in range(Q):
        x, y = map(int, input().split())
        print(path[x] + path[y])


if __name__ == "__main__":
    main()

Solution (Python):
import heapq
def dijkstra_heap(s):
    d = [float("inf")]*n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
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([z,y-1])
    edge[y-1].append([z,x-1])
Q,K = map(int,input().split())
L = dijkstra_heap(K-1)
query = []
for i in range(Q):
  query.append(list(map(int,input().split())))
for i in range(Q):
  print(L[query[i][0]-1]+L[query[i][1]-1])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = I()
a = IR(n)
l = a[0]
for i in range(1,n):
    g = gcd(l,a[i])
    l *= a[i]//g
print(l)
"""


n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = LI()
    a -= 1
    b -= 1
    v[a].append([b,c])
    v[b].append([a,c])
Q,k = LI()
d = [-1 for i in range(n)]
d[k-1] = 0
q = deque()
q.append(k-1)
while q:
    x = q.pop()
    for y,c in v[x]:
        if d[y] == -1:
            d[y] = d[x]+c
            q.append(y)
for i in range(Q):
    x,y = LI()
    x -= 1
    y -= 1
    print(d[x]+d[y])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = I()
a = IR(n)
l = a[0]
for i in range(1,n):
    g = gcd(l,a[i])
    l *= a[i]//g
print(l)
"""


def dijkstra(k):
    d[k] = 0
    q = [[0,k]]
    while q:
        dx,x = heappop(q)
        for y,c in v[x]:
            if d[y] > dx+c:
                d[y] = dx+c
                heappush(q,[d[y],y])

n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = LI()
    a -= 1
    b -= 1
    v[a].append([b,c])
    v[b].append([a,c])
q,k = LI()
d = [float("inf") for i in range(n)]
dijkstra(k-1)
for i in range(q):
    x,y = LI()
    x -= 1
    y -= 1
    print(d[x]+d[y])

Solution (Python):
from collections import*
input=open(0).readline
n=int(input())
e=[[]for _ in range(n)]
for _ 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())
d=[0]*n
f=[0]*n
f[k-1]=1
s=deque([(k-1,0)])
while s:
    t,c=s.pop()
    f[t]=1
    d[t]=c
    for i,v in e[t]:
        if not f[i]:
            s.append((i,v+c))
for _ in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Solution (Python):
from collections import*
input=open(0).readline
n=int(input())
e=[[]for _ in range(n)]
for _ 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())
d=[0]*n
f=[0]*n
f[k-1]=1
s=deque([(k-1,0)])
while s:
    t,c=s.pop()
    f[t]=1
    d[t]=c
    for i,v in e[t]:
        if not f[i]:
            s.append((i,v+c))
for _ in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Solution (Python):
def solve(N, ABCs, Q, K, XYs):
    path = [[] for _ in range(N + 1)]
    for (a, b, c) in ABCs:
        path[a].append((b, c))
        path[b].append((a, c))

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

    q = [K]
    while len(q):
        index = q.pop()
        for n, w in path[index]:
            if dst[n] == 0:
                dst[n] = dst[index] + w
                q.append(n)
    ans = []
    for x, y in XYs:
        ans.append(str(dst[x] + dst[y]))
    return "\n".join(ans)

if __name__ == "__main__":
    N = int(input())
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    Q, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, ABCs, Q, K, XYs))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

q, k = map(int, input().split())
depth = [-1 for _ in range(n)]

def dfs(v, p, d):
  depth[v] = d
  for to, c in ablist[v]:
    if to == p:
      continue
    dfs(to, v, d + c)

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

def dfs(n,p,d):
    visited[n] = True
    dist[n] = d
    for (i,c) in A[n]:
        if i != p and not visited[i]:
            dfs(i,n,d+c)

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

dist = [-1]*N
visited = [False]*N
dfs(K-1,N,0)

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

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]


from collections import defaultdict


for i in range(N-1):
    a,b,c = abc[i]
    con[a].append((b, c))
    con[b].append((a, c))

q = [(K,0)]
visited = [False] * (N+1)
visited[K] = True
costmap = [inf] * (N+1)
costmap[K] = 0
while q:
    n,cst = q.pop()
    for ch,chcst in con[n]:
        if visited[ch]:
            continue
        q.append( (ch, cst+chcst))
        visited[ch] = True
        costmap[ch]  = cst+ chcst
    





















for i in range(Q):
    x,y = xy[i]
    print( costmap[x] + costmap[y])

Solution (Python):
import sys

sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
g=[[]for i in range(n)]
for i 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))

def dijkstra(g,st):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1]))
    return dist

q,k=map(int,input().split())
dist=dijkstra(g,k-1)

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

Solution (Python):
import sys

sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
g=[[]for i in range(n)]
for i 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))

def dijkstra(g,st):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1]))
    return dist

q,k=map(int,input().split())
dist=dijkstra(g,k-1)

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