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):
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])

Solution (Python):
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])

Solution (Python):
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])

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


ad = {}
for n in range(N):
    ad[n+1]=[]
    
for n in range(N-1):
    a,b,c = list(map(int,input().split()))
    ad[a].append([b,c])
    ad[b].append([a,c])
    
Query = []
Q,K = list(map(int,input().split()))
for q in range(Q):
    x,y = list(map(int,input().split()))
    Query.append([x,y])


import heapq
INF = 10 ** 20

color = {}
for n in range(N):
    color[n+1] = -1
    
dist = {}
for n in range(N):
    dist[n+1] = INF

def dijkstra(start, node_num): 
    HP = []
    dist[start] = 0

    heapq.heappush(HP,[start,0])

    while HP:
        u = heapq.heappop(HP)[0]

        color[u] = 1

        for to, cost in ad[u]:
            if color[to] == -1 and dist[u] + cost < dist[to]:
                dist[to] = dist[u] + cost
                heapq.heappush(HP, (to, dist[to]))
    return dist

start = K
node_num = N
dist = dijkstra(start, node_num)

for x,y in Query:
    print(dist[x]+dist[y])

Solution (Python):

import sys

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


sys.setrecursionlimit(10**7)









INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7
def intread():
    return int(sysread())
def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return 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])

if __name__ == "__main__":
    run()

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



N=intput()
node=[list() for _ in range(N+1)]
for _ in range(N-1):
    a,b,c=mint()
    node[a].append([b,c])
    node[b].append([a,c])
Q,K=mint()
cost=[-1]*(N+1)
cost[K]=0
q=deque([K])
while q:
    u=q.popleft()
    for v,c in node[u]:
        if cost[v]<0:
            cost[v]=cost[u]+c
            q.append(v)
for _ in range(Q):
    x,y=mint()
    print(cost[x]+cost[y])

Solution (Python):
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])

Solution (Python):
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()  


def dijkstra(s, n): 
    dist = [inf] * n
    hq = [(0, s)] 
    dist[s] = 0
    seen = [False] * n 
    while hq:
        v = heappop(hq)[1] 
        seen[v] = True
        for to, cost in adj[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])

Solution (Python):
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()  


def dijkstra(s, n): 
    dist = [inf] * n
    hq = [(0, s)] 
    dist[s] = 0
    seen = [False] * n 
    while hq:
        v = heappop(hq)[1] 
        seen[v] = True
        for to, cost in adj[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])

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i 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())

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 = map(int,readline().split())
  print(dist[x - 1] + dist[y - 1])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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 = map(int, input().split())
    connection[a-1].append(branch(b-1, c))
    connection[b-1].append(branch(a-1, c))

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

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


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

Solution (Python):
from collections import deque
n=int(input())
num=[[] for _ in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    num[a-1].append([b,c])
    num[b-1].append([a,c])
q,k=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=map(int,input().split())
    print(ans[x-1]+ans[y-1])

Solution (Python):
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])

Solution (Python):
N=int(input())
tree=[[] for i in range(N)]
for i 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))
from collections import deque
visited=[-1 for i in range(N)]
Q,K=map(int,input().split())
visited[K-1]=0
q=deque([])
q.append(K-1)
while q:
  u=q.popleft()
  for v,d in tree[u]:
    if visited[v]==-1:
      visited[v]=visited[u]+d
      q.append(v)
    
for i in range(Q):
  x,y=map(int,input().split())
  print(visited[x-1]+visited[y-1])

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


N = int(input())
to = [[] for _ in range(N)]

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

Q, K = map(int, input().split())
K -= 1
query = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(Q)]
depth = [0] * N

def dfs(v, d, p=-1):
    depth[v] = d
    for cost, nv in to[v]:
        if nv == p:
            continue
        dfs(nv, d + cost, v)


def main():
    dfs(K, 0)
    for x, y in query:
        print(depth[x] + depth[y])


if __name__ == "__main__":
    main()

Solution (Python):
import sys

from collections import defaultdict
from heapq import heappop, heappush


class Dijkstra:
    """Graph input:
    {
    node:{node:cost,node:cost...},
    node:{node:cost,node:cost...},
    ...
    }
    """

    def __init__(self, graph: dict, N: int):
        self.graph = graph
        self.costs = [float("inf")] * N

    def calculate(self, start):
        queue = list()

        
        self.costs[start] = 0
        heappush(queue, (0, start))  

        while queue:
            
            cost_from_start, min_node = heappop(queue)

            
            for link, cost in self.graph[min_node].items():
                if cost_from_start + cost < self.costs[link]:
                    self.costs[link] = cost_from_start + cost
                    heappush(queue, (self.costs[link], link))

        return self.costs


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    graph = defaultdict(dict)
    for _ in range(n - 1):
        a, b, c = input_int_list()
        graph[a][b] = c
        graph[b][a] = c
    

    q, k = input_int_list()

    solver = Dijkstra(graph, n + 1)
    costs = solver.calculate(k)

    ans = []
    for _ in range(q):
        x, y = input_int_list()
        ans.append(costs[x] + costs[y])
    for i in ans:
        print(i)

    return


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n = int(input())
    G = {}
    for i in range(n):
        G[i+1] = []
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        G[a] += [[b,c]]
        G[b] += [[a,c]]
    q,k = 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 = map(int,input().split())
        print(dist[x-1]+dist[y-1])

if __name__ == "__main__":
    main()

Solution (Python):
def ij2str(i, j):
    return str(i) + '+' + str(j)

n = int(input())
tree = [[] for _ in range(n)]
dis = [0 for _ in range(n)]
c_list = {}
visited = set()
for i in range(n-1):
    a, b, c = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    c_list[ij2str(a-1, b-1)] = c
    c_list[ij2str(b-1, a-1)] = c

from collections import deque

q, k = map(int, input().split())
visited.add(k-1)
next = deque()
next.append(k-1)

while len(next):
    i = next.popleft()
    for j in tree[i]:
        if not j in visited:
            dis[j] = dis[i] + c_list[ij2str(i, j)]
            next.append(j)
            visited.add(j)

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

Solution (Python):
from collections import deque


def nearlist(N, LIST):  
    NEAR = [{} for _ in range(N)]
    for a, b, c in LIST:
        NEAR[a - 1][b - 1] = c
        NEAR[b - 1][a - 1] = c
    return NEAR


def bfs(NEAR, S, N):  
    DIST = [-1 for _ in range(N)]  
    DIST[S] = 0
    que, frag = deque([S]), set([S])

    while que:
        q = que.popleft()
        for i, c in NEAR[q].items():  
            if i in frag:  
                continue
            DIST[i] = DIST[q] + c
            que.append(i), frag.add(i)
    return DIST


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)]

near = nearlist(n, abc)
dist = bfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Solution (Python):
def nearlist(N, LIST):  
    NEAR = [{} for _ in range(N)]
    for a, b, c in LIST:
        NEAR[a - 1][b - 1] = c
        NEAR[b - 1][a - 1] = c
    return NEAR


def dfs(NEAR, S, N):  
    DIST = [-1 for _ in range(N)]  
    DIST[S] = 0
    stack, frag = [S], set([S])

    while len(stack) > 0:
        q = stack.pop()
        for i, c in NEAR[q].items():  
            if i in frag:  
                continue
            DIST[i] = DIST[q] + c
            stack.append(i), frag.add(i)
    return DIST


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)]

near = nearlist(n, abc)
dist = dfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Solution (Python):
from collections import deque


def nearlist(N, LIST):  
    NEAR = [{} for _ in range(N)]
    for a, b, c in LIST:
        NEAR[a - 1][b - 1] = c
        NEAR[b - 1][a - 1] = c
    return NEAR


def dfs(NEAR, S, N):  
    DIST = [-1 for _ in range(N)]  
    DIST[S] = 0
    stack, frag = [S], set([S])

    while len(stack) > 0:
        q = stack.pop()
        for i, c in NEAR[q].items():  
            if i in frag:  
                continue
            DIST[i] = DIST[q] + c
            stack.append(i), frag.add(i)
    return DIST


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)]

near = nearlist(n, abc)
dist = dfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Solution (Python):
from collections import deque


def nearlist(N, LIST):  
    NEAR = [{} for _ in range(N)]
    for a, b, c in LIST:
        NEAR[a - 1][b - 1] = c
        NEAR[b - 1][a - 1] = c
    return NEAR


def bfs(NEAR, S, N):  
    DIST = [-1 for _ in range(N)]  
    DIST[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i, c in NEAR[q].items():  
            if i in frag:  
                continue
            DIST[i] = DIST[q] + c
            que.append(i), frag.add(i)
    return DIST


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)]

near = nearlist(n, abc)
dist = bfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

itta=[0]*(n+1)
dic=defaultdict(list)
for a,b,c in abc:
    dic[a].append((b,c))
    dic[b].append((a,c))

d=deque([(k,0)])
while d:
    now=d.popleft()
    if itta[now[0]]!=0:
        continue
    itta[now[0]]=now[1]
    for i,j in dic[now[0]]:
        d.append((i,j+now[1]))

itta[k]=0
for x,y in xy:
    print(itta[x]+itta[y])

Solution (Python):
from collections import deque


def nearlist(N, LIST):  
    NEAR = [set() for _ in range(N)]
    COST = {}
    for a, b, c in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
        COST[(a - 1, b - 1)] = c
        COST[(b - 1, a - 1)] = c
    return NEAR, COST


def bfs(NEAR, S, N):  
    DIST = [-1 for _ in range(N)]  
    DIST[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  
            if i in frag:  
                continue
            DIST[i] = DIST[q] + cost[(q, i)]
            que.append(i), frag.add(i)
    return DIST


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)]

near, cost = nearlist(n, abc)
dist = bfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
from sys import stdin

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

n = int(input())
edge = [[] for _ in range(n)]
weight = [[] for _ in range(n)]
for _ in range(n-1):
    i, j, k = map(int, input().split())
    i -= 1
    j -= 1
    edge[i].append(j)
    edge[j].append(i)
    weight[i].append(k)
    weight[j].append(k)

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

k -= 1


distance = [-1] * n
distance[k] = 0
todo = [k]
while len(todo) > 0:
    i = todo.pop(-1)
    for j in range(len(edge[i])):
        if distance[edge[i][j]] == -1:
            distance[edge[i][j]] = distance[i] + weight[i][j]
            todo.append(edge[i][j])

ans = []
for _ in range(q):
    i, j = map(int, input().split())
    ans.append(distance[i-1] + distance[j-1])

for i in ans:
    print(i)

Solution (Python):
from sys import stdin
from sys import stdin
def input():
    return stdin.readline().strip()

n = int(input())
edge = [[] for _ in range(n)]
weight = [[] for _ in range(n)]
for _ in range(n-1):
    i, j, k = map(int, input().split())
    i -= 1
    j -= 1
    edge[i].append(j)
    edge[j].append(i)
    weight[i].append(k)
    weight[j].append(k)

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

k -= 1


distance = [-1] * n
distance[k] = 0
todo = [k]
while len(todo) > 0:
    i = todo.pop(-1)
    for j in range(len(edge[i])):
        if distance[edge[i][j]] == -1:
            distance[edge[i][j]] = distance[i] + weight[i][j]
            todo.append(edge[i][j])

ans = []
for _ in range(q):
    i, j = map(int, input().split())
    ans.append(distance[i-1] + distance[j-1])

for i in ans:
    print(i)

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

n=int(input())

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

q,k=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=map(int, input().split())
    x-=1
    y-=1
    print(dist[x]+dist[y])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
""" ABC070D Transit Tree Path
"""
from collections import deque
from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    """
    優先度付きキューの
    """
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self, item):
        heappush(self.heap, item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self, item):
        return heappushpop(self.heap, item)
    
    def __call__(self):
        return self.heap
    
    def __len__(self):
        return len(self.heap)


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())
INF = float("inf")


def dijkstra(adj: list, s: int):
    Color = [0]*N 
    D = [INF]*N 
    P = [None]*N 

    D[s] = 0
    P[s] = None
    PQ = PriorityQueue([(0, s)]) 

    while PQ: 

        min_cost, u = PQ.pop() 

        Color[u] = 2 

        if D[u] < min_cost:
            
            continue

        for adj_idx, adj_w in adj[u]:
            if Color[adj_idx] != 2: 
                if D[u] + adj_w < D[adj_idx]: 
                    D[adj_idx] = D[u] + adj_w
                    P[adj_idx] = u
                    
                    PQ.push((D[adj_idx], adj_idx))
                    Color[adj_idx] = 1
    
    return D, P

D, P = dijkstra(G, s=K-1)
for q in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(D[x]+D[y])

Solution (Python):
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) 
	cost = [float('inf')] * n 
	cost[s] = 0 
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: 
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])

Solution (Python):
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])