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):
import heapq

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

q, k = map(int, input().split())
XY = []
for _ in range(q):
    x, y = map(int, input().split())
    XY.append([x,y])


def dijkstra_heap(s, Edge):
    Dist = [10**10 for _ in range(n+1)]
    Dist[s] = 0
    Used = [False for _ in range(n+1)]
    Used[s] = True

    Edgelist = []

    for edge in Edge[s]:
        heapq.heappush(Edgelist, edge)

    while len(Edgelist) >= 1:
        minedge = heapq.heappop(Edgelist)
        cost, v = minedge[0], minedge[1]
        if Used[v] == True:
            continue
        Used[v] = True
        Dist[v] = cost

        for next_edge in Edge[v]:
            next_cost = next_edge[0]
            next_v = next_edge[1]
            heapq.heappush(Edgelist, [next_cost + Dist[v], next_v])
    return Dist


Dist_k = dijkstra_heap(k, Edge)

for xy in XY:
    x = xy[0]
    y = xy[1]
    ans = Dist_k[x] + Dist_k[y]
    print(ans)

Solution (Python):

n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append([b,c])
  peer[b].append([a,c])
q,k = map(int,input().split())
k -= 1
now = [k]
seen = [0 for _ in range(n)]
way = [0 for _ in range(n)]
seen[k] = 1
while now:
  last = now
  now = []
  for x in last:
    for yc in peer[x]:
      y,c = yc
      if seen[y] == 0:
        seen[y] = 1
        way[y] = way[x] + c
        now.append(y)

for _ in range(q):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  print(way[a]+way[b])

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(1000000)
    n=int(input())
    edges=[[] for _ in range(n)]
    for i 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())
    k-=1
    
    dist=[10**9+1]*n
    dist[k]=0
    
    def dfs(s,before=-1):
       for edge in edges[s]:
           to=edge[0]
           c=edge[1]
           if to!=before:
               dist[to]=dist[s]+c
               dfs(to,s) 
              
    dfs(k)
    for i in range(q):
        x,y=map(int,input().split())
        x-=1
        y-=1
        print(dist[x]+dist[y])
        
if __name__=='__main__':
    main()

Solution (Python):
import heapq
def dijkstra(V, edges, s):
    inf=float('inf')

    dist=[inf]*V
    dist[s]=0
    
    que=[[0,s]]
    heapq.heapify(que) 

    while  que:
        p=heapq.heappop(que) 
        dis=p[0]
        v=p[1]
        if dist[v] <dis:
            continue
        for edge in edges[v]:
            to_v=edge[0]
            cost=edge[1]
        
            if dist[to_v] > dist[v] + cost:
                dist[to_v]=dist[v]+cost
                heapq.heappush(que,[dist[to_v], to_v])
    
    return dist

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    edges=[[] for _ in range(n)]
    for i 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())
    k-=1
   
    dist=dijkstra(n,edges,k)
    for i in range(q):
        x,y=map(int,input().split())
        x-=1
        y-=1
        print(dist[x]+dist[y])
if __name__=='__main__':
    main()

Solution (Python):
import heapq
def dijkstra(V, edges, s):
    inf=float('inf')

    dist=[inf]*V
    dist[s]=0
    
    que=[[0,s]]
    heapq.heapify(que) 

    while  que:
        p=heapq.heappop(que) 
        dis=p[0]
        v=p[1]
        if dist[v] <dis:
            continue
        for edge in edges[v]:
            to_v=edge[0]
            cost=edge[1]
        
            if dist[to_v] > dist[v] + cost:
                dist[to_v]=dist[v]+cost
                heapq.heappush(que,[dist[to_v], to_v])
    
    return dist

def main():
    n=int(input())
    edges=[[] for _ in range(n)]
    for i 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())
    k-=1
   
    dist=dijkstra(n,edges,k)
    for i in range(q):
        x,y=map(int,input().split())
        x-=1
        y-=1
        print(dist[x]+dist[y])
if __name__=='__main__':
    main()

Solution (Python):


import sys
sys.setrecursionlimit(10**9)

def dfs(num,cost):
    visited[num]=cost
    for item in way[num]:
        if visited[item[0]]==-1:
            dfs(item[0],cost+item[1])
    return
    
N=int(input())

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


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

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""



import heapq

def dijkstra():
    
    
    n = onem()
    edge = [[] for i in range(n)]
    dg = 10**7
    
    for i in range(n-1):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        edge[x].append(z*dg + y)
        edge[y].append(z*dg + x)
    q,w = m()
    s = w-1
    d = [-1]*n
    d[s] = 0

    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)

        

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        v,c = minedge%dg,minedge//dg
        if d[v] >= 0:
            continue
        d[v] = c
        for e in edge[v]:
            vNext = e%dg
            if d[vNext]:
                heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)

    

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


def warshall_floyd(n,d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

dijkstra()

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())
    x-=1
    y-=1
    edge[x].append([z,y])
    edge[y].append([z,x])

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

d = dijkstra_heap(K-1)
for q 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())
inf = float("inf")
tree = [[] for _ in range(n+1)]
for _ 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())

depth = [inf] * (n+1)
visited = [False] * (n+1)
depth[k] = 0
queue = deque([k])
while queue:
    now = queue.popleft()
    visited[now] = True
    for i, v in tree[now]:
        if visited[i]:
            pass
        else:
            queue.append(i)
            depth[i] = min(depth[i], depth[now] + v)
for _ in range(q):
    x, y = map(int, input().split())
    ans = depth[x] + depth[y]
    print(ans)

Solution (Python):
n = int(input())
inf = float("inf")
tree = [[] for _ in range(n+1)]
for _ 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())

depth = [inf] * (n+1)
visited = [False] * (n+1)
depth[k] = 0
stack = [k]
while stack:
    now = stack.pop()
    visited[now] = True
    for i, v in tree[now]:
        if visited[i]:
            pass
        else:
            stack.append(i)
            depth[i] = min(depth[i], depth[now] + v)
for _ in range(q):
    x, y = map(int, input().split())
    ans = depth[x] + depth[y]
    print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline()[:-1]

from collections import defaultdict

sys.setrecursionlimit(10 ** 7)


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(set)
n = int(input())
for i in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].add((b, c))
    tree[b].add((a, c))

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


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

Solution (Python):
import sys
input = lambda: sys.stdin.readline()[:-1]

from collections import defaultdict

sys.setrecursionlimit(10 ** 7)


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(list)
n = int(input())
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

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

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

def input():
    return sys.stdin.readline()[:-1]


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(list)
n = int(input())
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

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

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

def input():
    return sys.stdin.readline()[:-1]


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(list)
n = int(input())
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

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

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(list)
n = int(input())
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

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

Solution (Python):
n = int(input())
abc=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    abc.append(tmp)
q,k = map(int, input().split())
que = []
for i in range(q):
    tmp = list(map(int,input().split()))
    que.append(tmp)

link = [[] for _ in range(n)]
for tmp in abc:
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,tmp[2]])

dist=[-1]*n

from collections import deque
Q = deque()
Q.append([k-1,0])

while Q:
    now,now_d=Q.popleft()

    for nxt in link[now]:
        if dist[nxt[0]]!=-1:
            continue
        nxt_d =nxt[1] + now_d
        dist[nxt[0]]=nxt_d
        Q.append([nxt[0],nxt_d])

for tmp in que:
    print(dist[tmp[0]-1] + dist[tmp[1]-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N = int(input())
Edges = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    Edges[a].append((b,c))
    Edges[b].append((a,c))
D = [float('inf') for i in range(N)]
def dfs(v,p,d):
    D[v] = d
    for e1,e2 in Edges[v]:
        if e1 != p:
            dfs(e1,v,d+e2)
Q,K = map(int,input().split())
dfs(K-1,-1,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(D[x-1]+D[y-1])

Solution (Python):
from collections import defaultdict, deque

N = int(input())
neighbors = defaultdict(list)
for i in range(N - 1):
    ai, bi, ci = map(int, input().split())
    ai -= 1
    bi -= 1
    neighbors[ai].append((bi, ci))
    neighbors[bi].append((ai, ci))
Q, K = map(int, input().split())
K -= 1
queries = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(Q)]

queue = deque([K])
d = [0] * N
while len(queue) > 0:
    v = queue.pop()
    for child, ci in neighbors[v]:
        if child == K or d[child] != 0:
            continue
        d[child] = d[v] + ci
        queue.append(child)

for xi, yi in queries:
    print(d[xi] + d[yi])

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
import sys
input = sys.stdin.readline
n =int(input())

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

for i in range(n-1):
    a, b, c = map(int,input().split())
    a, b = a-1, b-1
    edge[a].append([c,b])
    edge[b].append([c,a]) 
q, k = map(int, input().split())
k = k-1
d = dijkstra_heap(k)
for i in range(q):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  print(d[x]+d[y])

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
import sys
input = sys.stdin.readline
n =int(input())

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

for i in range(n-1):
    a, b, c = map(int,input().split())
    a, b = a-1, b-1
    edge[a].append([c,b])
    edge[b].append([c,a]) 
q, k = map(int, input().split())
k = k-1
d = dijkstra_heap(k)
for i in range(q):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  print(d[x]+d[y])

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
B=[list(map(int,input().split())) for i in range(Q)]
C=[[]for i in range(N)]
for a,b,c in A:
  a-=1
  b-=1
  C[a].append((b,c))
  C[b].append((a,c))
  
Q=[-1 for i in range(N)]
Q[K-1]=0
que=deque()
que.append(K-1)
while que:
  x=que.popleft()
  for i,j in C[x]:
    if Q[i]==-1:
      que.append(i)
      Q[i]=Q[x]+j
for x,y in B:
  print(Q[x-1]+Q[y-1])

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


n = int(input())
edges = [[] for _ in range(n)]

for _ in range(n-1):
    _from, to, dist = map(int, input().split())
    edges[_from-1].append([to-1, dist])
    edges[to-1].append([_from-1, dist])

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

distance_from_k_to = [10**7] * n
distance_from_k_to[k] = 0

todo = []
while edges[k]:
    to, dist = edges[k].pop()
    todo.append([to, dist])

while todo:
    node, dist = todo.pop()
    if distance_from_k_to[node] != 10**7:  
        continue

    distance_from_k_to[node] = dist
    while edges[node]:
        to, add_dist = edges[node].pop()
        todo.append([to, dist+add_dist])

for _ in range(q):
    start, goal = map(int, input().split())
    start, goal = start-1, goal-1
    ans = distance_from_k_to[start] + distance_from_k_to[goal]
    print(ans)

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


n = int(input())
edges = [[] for _ in range(n)]

for _ in range(n-1):
    _from, to, dist = map(int, input().split())
    edges[_from-1].append([to-1, dist])
    edges[to-1].append([_from-1, dist])

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

distance_from_k_to = [10**7] * n
distance_from_k_to[k] = 0

todo = []
while edges[k]:
    to, dist = edges[k].pop()
    todo.append([to, dist])

while todo:
    node, dist = todo.pop()
    if distance_from_k_to[node] != 10**7:  
        continue

    distance_from_k_to[node] = dist
    while edges[node]:
        to, add_dist = edges[node].pop()
        todo.append([to, dist+add_dist])

for _ in range(q):
    start, goal = map(int, input().split())
    start, goal = start-1, goal-1
    ans = distance_from_k_to[start] + distance_from_k_to[goal]
    print(ans)

Solution (Python):
n = int(input())
edges = [[] for _ in range(n)]

for _ in range(n-1):
    _from, to, dist = map(int, input().split())
    edges[_from-1].append([to-1, dist])
    edges[to-1].append([_from-1, dist])

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

distance_from_k_to = [10**7] * n
distance_from_k_to[k] = 0

todo = []
while edges[k]:
    to, dist = edges[k].pop()
    todo.append([to, dist])

while todo:
    node, dist = todo.pop()
    if distance_from_k_to[node] != 10**7:  
        continue

    distance_from_k_to[node] = dist
    while edges[node]:
        to, add_dist = edges[node].pop()
        todo.append([to, dist+add_dist])

for _ in range(q):
    start, goal = map(int, input().split())
    start, goal = start-1, goal-1
    ans = distance_from_k_to[start] + distance_from_k_to[goal]
    print(ans)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
p = [deque([]) for _ in range(N)]

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

Q, K = [int(x) for x in input().strip().split()]

c = [-1] * N
f = [False] * N

def search(cp, cost):
    f[cp-1] = True
    for np, cos in p[cp-1]:
        if f[np-1]:
            continue
        c[np-1] = cost + cos
        f[np-1] = True
        search(np, cost + cos)

search(K, 0)
for q in range(Q):
    x, y = [int(x) for x in input().strip().split()]
    print(c[x-1]+c[y-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  edges[a-1].append((b-1,c))
  edges[b-1].append((a-1,c))
q,k=map(int,input().split())
depth=[0]*n
def dfs(child,parent,d):
  if edges[child]==parent:
    return
  depth[child]=d
  for newchild,distance in edges[child]:
    if newchild==parent:
      continue
    dfs(newchild,child,d+distance)
  return
dfs(k-1,-1,0)
for i in range(q):
  x,y=map(int,input().split())
  x-=1
  y-=1
  ans=depth[x]+depth[y]
  print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e15)


def bfs(s, g, N, G):

    return 0


def main():
    
    N = Scanner.int()
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b, c = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append((b, c))
        G[b].append((a, c))
    Q, K = Scanner.map_int()
    K -= 1
    length = [0] * N
    q = []
    q.append(K)
    while q != []:
        i = q.pop()
        for n in G[i]:
            if length[n[0]] != 0:
                continue
            length[n[0]] = length[i] + n[1]
            q.append(n[0])
    query = Scanner.int_list_list(Q)
    for q in query:
        print(length[q[0] - 1] + length[q[1] - 1])
    return


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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(readline()) 

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

for i in range(n-1):
    x,y,z = map(int,readline().split()) 
    x,y = x-1,y-1 
    edge[x].append([z,y])
    edge[y].append([z,x]) 

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

fromk = dijkstra_heap(k-1)



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

Solution (Python):
from collections import defaultdict, deque
N = int(input())
dic = defaultdict(list)
for i in range(N-1):
  a, b, c = map(int, input().split())
  dic[a-1] += [(b-1,c)]
  dic[b-1] += [(a-1,c)]
Q, K = map(int, input().split())
deq = deque([(K-1,0)])
dist = [-1]*N
while deq:
  p, d = deq.popleft()
  for e, dd in dic[p]:
    if dist[e]==-1:
      dist[e] = d + dd
      deq += [(e,d+dd)]
for i in range(Q):
  x, y = map(int, input().split())
  print(dist[x-1]+dist[y-1])

Solution (Python):
import sys

input = sys.stdin.readline

d = []
ABC = []

sys.setrecursionlimit(10 ** 8)


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

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


if __name__ == '__main__':
    main()

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

def dfs(v: int, p: int = -1, s: int = 0):
    dist[v] = s
    for i, j in t[v]:
        if i == p:
            continue
        dfs(i, v, s + j)

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

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

dist = [0]*n

dfs(k)

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

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

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

depth = [0 for _ in range(n)]
def dfs(v, p = -1, d = 0):
  depth[v] = d
  for i, j in abc[v]:
    if i == p:
      continue
    dfs(i, v, d+j)
dfs(k)


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

Solution (Python):
from collections import deque
def bfs(s):
	que = deque([])
	que.append(s-1)
	while que:
		v = que[0]
		que.popleft()
		for b, c in d[v]:
			if l[b] == 0:
				l[b] = l[v] + c
				que.append(b)
n = int(input())
l = [0 for i in range(n)]
d = [[] for i in range(n)]
for i in range(n-1):
	a, b, c = map(int, input().split())
	d[a-1].append((b-1,c))
	d[b-1].append((a-1,c))
q, k = map(int ,input().split())
bfs(k)

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import defaultdict, deque
    N = int(input())
    G = [[] for i in range(N)]
    cost = defaultdict(int)
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cost[a-1, b-1] = c
        cost[b-1, a-1] = c
    Q, K = (int(i) for i in input().split())
    dist = [-1 for _ in range(len(G))]

    def bfs(s):
        que = deque()
        dist[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + cost[v, u]
                que.append(v)

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
N = int(input())
g = [[] for x 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 = [-1] * (N+1)
d[K] = 0
r = deque()

r.append(K)
while len(r) > 0:
  i = r.popleft()
  for v in g[i]:
    if(d[v[0]] == -1):
      d[v[0]] = d[i] + v[1]
      r.append(v[0])

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

Solution (Python):
N= int(input())
abc = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    abc[a].append((b,c))
    abc[b].append((a,c))
    
def dijkstra(node,start,abc):
    import heapq
    d = [float('inf') for i in range(N)]
    d[start] = 0
    d2 = [(0,start)]
    heapq.heapify(d2)
    while d2:
        c,v = heapq.heappop(d2)
        if d[v] < c:
            continue
        for t,cost in abc[v]:
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heapq.heappush(d2,(d[t],t))
    return d

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

Solution (Python):
from collections import deque

def solve(n, ABC, q, k, XY):
    graph = [[] for _ in range(n)]
    for a, b, c in ABC:
        graph[a - 1].append((b - 1, c))
        graph[b - 1].append((a - 1, c))

    q = deque(maxlen=n)
    q.append((k - 1, 0))
    used = {k - 1}
    l = [0] * n
    while len(q) > 0:
        node, length = q.popleft()
        l[node] = length
        for next, next_length in graph[node]:
            if next in used:
                continue
            q.append((next, length + next_length))
            used.add(next)

    return [l[x - 1] + l[y - 1] for x, y in XY]

_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)]
print(*solve(_n, _ABC, _q, _k, _XY), sep='\n')