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 heapq import heappush, heappop
from collections import defaultdict

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


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



INF = 1 << 60
dist = [INF] * (n + 1)
dist[k] = 0


que = [(0, k)]


while que:
    cost, curr = heappop(que)
    if cost > dist[curr]:
        continue
    for after, nc in graph[curr]:
        if cost + nc < dist[after]:
            dist[after] = cost + nc
            heappush(que, (cost + nc, after))
            
print(*([dist[x] + dist[y] for x, y in (map(int, input().split()) for _ in range(q))]), sep="\n")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(now, vis, dis):
    for to,c in edge[now]:
        if not vis[to]:
            if dis[to] == 0:
                dis[to] = dis[now] + c
            else:
                dis[to] = min(dis[now] + c, dis[to])
            vis[now] = 1
            dfs(to, vis, dis)

N = int(input())

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

visited = [0]*N
distance = [0]*N

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



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

Solution (Python):
N=int(input())
import sys
sys.setrecursionlimit(10**6)
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())
D=[-1]*N
D[K-1]=0
def dfs(start, nowd):
    to=T[start]
    for t in to:
        next_node,c=t
        if D[next_node]!=-1:
            continue
        nextd=nowd+c
        D[next_node]=nextd
        dfs(next_node, nextd)
dfs(K-1,0)

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])

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

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




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 

d = dijkstra_heap(K)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
def dfs(parent,current,distance):
  global m
  m[current]=distance
  for child in graph[current]:
    if child[0]==parent:
      continue
    dfs(current,child[0],distance+child[1])
n=int(input())
graph=[]
for i in range(n+1):
  graph.append([])
m=[0]*(n+1)
for i 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())
dfs(k,k,0)
for i in range(q):
  x,y=map(int,input().split())
  print(m[x]+m[y])

Solution (Python):
import sys

import math


import heapq




input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007


def dijkstra(graph, start, n):
    h = []
    heapq.heappush(h, (0, start))
    costs = [INF for _ in range(n)]
    while h:
        cost, cur = heapq.heappop(h)
        if costs[cur] != INF:
            continue
        costs[cur] = cost
        for edge in graph[cur]:
            ecost, tgt = edge
            if costs[tgt] == INF:
                heapq.heappush(h, (cost + ecost, tgt))

    return costs

def solve():
    n = getN()
    graph = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c = getList()
        a,b = a-1, b-1

        graph[a].append([c, b])
        graph[b].append([c, a])
    q, k = getList()
    costs = dijkstra(graph, k-1, n)
    
    for i in range(q):
        s, e = getZList()

        print(costs[s] + costs[e])

    return

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    
    solve()

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

N = int(input())
tree = [[] for _ 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))

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

dis = [-1]*N
dis[K-1] = 0
def dfs(v,d):
    for i in tree[v]:
        d = dis[v]
        next,c = i
        if dis[next] == -1:
            d += c
            dis[next] = d
            dfs(next,d)
dfs(K-1,0)

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

Solution (Python):
from collections import deque

n = int(input())
ab = [[]for i in range(10**5)]
v=[0]*(10**5)
d=[float('INF')]*(10**5)
for i in range(n-1):
    a , b , c = map(int, input().split())
    ab[a-1].append((b-1,c))
    ab[b-1].append((a-1,c))
q , k = map(int, input().split())

k-=1
de=deque()
de.append((k,0))

d[k]=0
while de:
    now , dis = de.popleft()
    if dis > d[now]:
        continue

    for next , cost in ab[now]:
        if dis + cost < d[next]:
            d[next]= dis + cost
            de.append((next,dis+cost))

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

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

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]*n
dist[k] = 0
def dfs(now):
    for nxt,d in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now] + d
        dfs(nxt)
dfs(k)

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

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

Solution (Python):
from collections import deque

n = int(input())
d = {i: [] for i in range(1, n+1)}
for _ in range(n-1):
    a, b, c = map(int, input().split())
    d[a].append((b, c))
    d[b].append((a, c))
q, k = map(int, input().split())
D = [-1] * (n + 1)
D[k] = 0
que = deque([k])
while que:
    t = que.popleft()
    dist = D[t]
    for l, c in d[t]:
        if D[l] < 0:
            D[l] = dist + c
            que.append(l)
for _ in range(q):
    x, y = map(int, input().split())
    print(D[x] + D[y])

Solution (Python):
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(1000000)
    n, *rem = map(int, open(0).read().split())
    t = 3 * (n - 1)
    abc = rem[:t]
    q, k = rem[t], rem[t + 1]
    xy = rem[t + 2:]

    dist = defaultdict(dict)
    for a, b, c in zip(*[iter(abc)] * 3):
        dist[a].update({b: c})
        dist[b].update({a: c})

    vis = [False] * (n + 1)
    cost = [0] * (n + 1)
    vis[k] = True

    def dfs(a, b):
        if vis[b]:
            return
        vis[b] = True
        cost[b] = cost[a] + dist[a][b]
        a = b
        for b in dist[a].keys():
            dfs(a, b)

    for b in dist[k].keys():
        dfs(k, b)

    tmp = []
    for x, y in zip(*[iter(xy)] * 2):
        tmp.append(cost[x] + cost[y])

    ans = "\n".join(map(str, tmp))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(1000000)
    n, *rem = map(int, open(0).read().split())
    t = 3 * (n - 1)
    abc = rem[:t]
    q, k = rem[t], rem[t + 1]
    xy = rem[t + 2:]

    m = [[] for _ in range(n + 1)]
    dist = defaultdict(dict)
    for a, b, c in zip(*[iter(abc)] * 3):
        m[a].append(b)
        m[b].append(a)

        dist[a].update({b: c})
        dist[b].update({a: c})

    vis = [False] * (n + 1)
    cost = [0] * (n + 1)
    vis[k] = True

    def dfs(frm, to):
        if vis[to]:
            return
        vis[to] = True
        cost[to] = cost[frm] + dist[frm][to]
        frm = to
        for to in m[frm]:
            dfs(frm, to)

    frm = k
    for to in m[frm]:
        dfs(frm, to)

    tmp = []
    for x, y in zip(*[iter(xy)] * 2):
        tmp.append(cost[x] + cost[y])

    ans = "\n".join(map(str, tmp))
    print(ans)


if __name__ == '__main__':
    main()

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

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

limit = 100010
depth = [0] * limit

def dfs(v, p, d): 
    depth[v] = d
    for e in tree[v]:
        if e[0] == p: continue
        dfs(e[0], v, d + e[1])

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

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

from heapq import heappush, heappop
INF = 10 ** 18
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 tree[v]: 
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

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

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from heapq import heappop, heappush
def dijkstra(E,s,n,inf=float('inf')):
    d = [inf]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,dist in E[u]:
            dnew = du + dist
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d

N = I()
a,b,c = LIR(N-1,3)
Q,K = LI()
x,y = LIR(Q,2)

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

d = dijkstra(E,K-1,N,inf=10**9*(N-1)+1)

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

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from heapq import heappop, heappush
def dijkstra(E,s,n):
    d = [float('inf')]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,weight in E[u].items():
            dnew = du + weight
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d

N = I()
a,b,c = LIR(N-1,3)
Q,K = LI()
x,y = LIR(Q,2)

E = [dict() for _ in range(N)]
for i in range(N-1):
    E[a[i]-1][b[i]-1] = c[i]
    E[b[i]-1][a[i]-1] = c[i]

d = dijkstra(E,K-1,N)

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

Solution (Python):
def dijkstra_list(graph, startidx):
    
    n_nodes = len(graph)
    
    
    nodes = []
    for i in range(n_nodes):
        nodes.append([
            float("inf"), 
            None,         
            False,        
            i             
        ])

    
    import heapq
    priority_queue = []
    heapq.heapify(priority_queue)

    
    nodes[startidx][0] = 0
    nodes[startidx][1] = None
    nodes[startidx][2] = True

    
    for dst, cost in graph[startidx]:
        if nodes[dst][0] > nodes[startidx][0]+cost:
            nodes[dst][0] = nodes[startidx][0]+cost
            nodes[dst][1] = startidx
            heapq.heappush(priority_queue, nodes[dst])
    
    
    
    
    n_done = 1
    while priority_queue:
        if n_done == n_nodes:
            break

        node = heapq.heappop(priority_queue)
        if node[2]: 
            continue
        
        node[2] = True
        n_done += 1

        for dst, cost in graph[node[3]]:
            if nodes[dst][0] > nodes[node[3]][0]+cost:
                nodes[dst][0] = nodes[node[3]][0]+cost
                nodes[dst][1] = node[3]
                heapq.heappush(priority_queue, nodes[dst])

    costs = [node[0] for node in nodes]
    froms = [node[1] for node in nodes]
    return  costs, froms

def resolve():
    N = int(input())
    adjs = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = list(map(int, input().split()))
        adjs[a-1].append([b-1, c])
        adjs[b-1].append([a-1, c])
    Q, K = list(map(int, input().split()))
    queries = [list(map(int, input().split())) for _ in range(Q)]
    costs, _ = dijkstra_list(adjs, K-1)
    for q in queries:
        print(costs[q[0]-1]+costs[q[1]-1])


if '__main__' == __name__:
    resolve()

Solution (Python):
from collections import deque
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n=int(input())

tree=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=nii()
  a-=1
  b-=1
  tree[a].append([b,c])
  tree[b].append([a,c])

q,k=nii()
k-=1

dist=[-1 for i in range(n)]
dist[k]=0

que=deque()
que.append(k)

while que:
  x=que.popleft()
  for tb,tc in tree[x]:
    if dist[tb]==-1:
      que.append(tb)
      dist[tb]=dist[x]+tc

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

Solution (Python):

import sys
sys.setrecursionlimit(200000)

def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    edges = [[] for _ in range(N+1)]
    for aa, bb, cc in zip(a, b, c):
        edges[aa].append((bb, cc))
        edges[bb].append((aa, cc))
    costs = [None] * (N + 1)
    def dfs(n, cost):
        if costs[n] is not None:
            return
        costs[n] = cost
        for nn, cc in edges[n]:
            dfs(nn, cost+cc)
    dfs(K, 0)
    for xx, yy in zip(x, y):
        print(costs[xx]+costs[yy])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N - 1)  
    b = [int()] * (N - 1)  
    c = [int()] * (N - 1)  
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  
    K = int(next(tokens))  
    x = [int()] * (Q)  
    y = [int()] * (Q)  
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
from collections import deque
import sys
def input():
    return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append([b, c])
        G[b].append([a, c])
    q, k = list(map(int, input().split()))
    k -= 1
    stack = deque([k, ])
    ans = [-1] * n
    ans[k] = 0
    while stack:
        x = stack.popleft()
        for (dx, l) in G[x]:
            if ans[dx] == -1:
                ans[dx] = ans[x] + l
                stack.appendleft(dx)
    for _ in range(q):
        x, y = list(map(lambda x: int(x) - 1, input().split()))
        print(ans[x] + ans[y])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
def input():
    return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append([b, c])
        G[b].append([a, c])
    q, k = list(map(int, input().split()))
    k -= 1
    stack = deque([k, ])
    ans = [-1] * n
    ans[k] = 0
    while stack:
        x = stack.popleft()
        for (dx, l) in G[x]:
            if ans[dx] == -1:
                ans[dx] = ans[x] + l
                stack.appendleft(dx)
    for _ in range(q):
        x, y = list(map(lambda x: int(x) - 1, input().split()))
        print(ans[x] + ans[y])

if __name__ == '__main__':
    main()

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()


def dijkstra(n,s,edge):
  d=[inf]*n
  used=[False]*n
  d[s]=0
  used[s]=True
  pq=[]
  for e in edge[s]:
    heapq.heappush(pq,e)
  while pq:
    c,v=heapq.heappop(pq)
    if used[v]:
      continue
    d[v]=c
    used[v]=True
    for nc,nv in edge[v]:
      if not used[nv]:
        nd=nc+c
        if d[nv]>nd:
          heapq.heappush(pq,(nd,nv))
  return d


def main():
  n=I()
  e=[[] for _ in range(n)]
  for _ in range(n-1):
    a,b,c=LI()
    a-=1
    b-=1
    e[a].append((c,b))
    e[b].append((c,a))

  q,k=LI()
  d=dijkstra(n,k-1,e)

  ans=[]
  for _ in range(q):
    x,y=LI()
    x-=1
    y-=1
    dist=d[x]+d[y]
    ans.append(dist)

  for x in ans:
    print(x)

main()

Solution (Python):
from collections import defaultdict
from collections import deque

N = int(input())

neighbor = defaultdict(dict)

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

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

dp = [-1] * N

d = deque()
d.append((K, 0, -1))

while d:
    i, cost, parent = d.pop()

    dp[i] = cost

    for j, c in neighbor[i].items():
        if j != parent:
            d.append((j, cost+c, i))

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

Solution (Python):
def main():
    import sys

    def I():
        return int(sys.stdin.readline().rstrip())

    def S():
        return sys.stdin.readline().rstrip()

    N = I()
    G = [[] for i in range(N + 1)]

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

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

    from collections import deque

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

    q = deque([K])
    while q:
        a = q.pop()
        for b, c in G[a]:
            if distance[b] != -1:
                continue
            distance[b] = distance[a] + c
            q.appendleft(b)

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())
def S(): return sys.stdin.readline().rstrip()

N = I()
G = [[] for i in range(N+1)]

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

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

from collections import deque

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

q = deque([K])
while q:
    a = q.pop()
    for b,c in G[a]:
        if distance[b] != -1:
            continue
        distance[b] = distance[a] + c
        q.appendleft(b)

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

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())
def S(): return sys.stdin.readline().rstrip()

N = I()
G = {}
for i in range(1,N+1):
    G[i] = []
for i in range(N-1):
    a,b,c = map(int,S().split())
    G[a].append((b,c))
    G[b].append((a,c))

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

from collections import deque

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

q = deque([K])
while q:
    a = q.pop()
    for b,c in G[a]:
        if distance[b] != -1:
            continue
        distance[b] = distance[a] + c
        q.appendleft(b)

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

Solution (Python):
from collections import deque
n = int(input())
route = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    route[a].append((b,c))
    route[b].append((a,c))
q,k = map(int,input().split())
ans = [-1 for i in range(n+1)]
ans[k] = 0
d = deque()
d.append((k,0))
while d:
    now,cost = d.popleft()
    for i , j in route[now]:
        if ans[i] == -1:
            ans[i] = cost+j
            d.append((i,cost+j))
for i in range(q):
    x,y = map(int,input().split())
    print(ans[x]+ans[y])

Solution (Python):
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s,d=map(int,input().split())
    edges[a-1].append((s-1,d));edges[s-1].append((a-1,d))
q,k=map(int,input().split())
cost=[0]*n
from collections import deque
dq=deque([])

for to,cos in edges[k-1]:
    dq.append((k-1,to))
    cost[to]=cos
while dq:
    par,now=dq.popleft()
    
    for to,c in edges[now]:
        if to!=par:
            cost[to]=cost[now]+c
            dq.append((now,to))

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

Solution (Python):
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s,d=map(int,input().split())
    edges[a-1].append((s-1,d));edges[s-1].append((a-1,d))
q,k=map(int,input().split())
cost=[0]*n
from collections import deque
dq=deque([])

for to,cos in edges[k-1]:
    dq.append((k-1,to))
    cost[to]=cos
while dq:
    par,now=dq.popleft()
    
    for to,c in edges[now]:
        if to!=par:
            cost[to]=cost[now]+c
            dq.append((now,to))

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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N = int(input())
a = [[] for i in range(N)]
for i 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])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    ans.append(dist[x-1]+dist[y-1])
  print(*ans, sep = "\n")

if __name__ == "__main__":
  main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N = int(input())
a = [[] for i in range(N)]
for i 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])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

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

if __name__ == "__main__":
  main()

Solution (Python):
import heapq

n = int(input())

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

    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))

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

dis = [float("inf")] * n
dis[k-1] = 0
pq = [(0, k-1)]
while pq:
    d, node = heapq.heappop(pq)
    if d > dis[node]: continue

    for nxt, cost in g[node]:
        if d + cost < dis[nxt]:
            dis[nxt] = d + cost
            heapq.heappush(pq, (dis[nxt], nxt))

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

    ans.append(dis[x-1]+dis[y-1])

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

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


def dfs(node, dis, adj_list):

    for next, d in adj_list[node]:
        if dis[next] == float("inf"):
            dis[next] = dis[node] + d
            dfs(next, dis, adj_list)

    return


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


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

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

k -= 1
dis = [float("inf")] * n
dis[k] = 0
dfs(k, dis, adj_list)

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

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

n = int(input())
edges = [[] for _ in range(n)]
costs = [-1]*n
def dfs(current):

    for nex, cost in edges[current]:
        if costs[nex] != -1:
            continue
        costs[nex] = costs[current] + cost
        dfs(nex)

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
costs[k] = 0
dfs(k)

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

for ans in res:
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n = int(input())
to = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    to[a].append((b, c))
    to[b].append((a, c))

q, k = map(int, input().split())
dist_k = [0] + [-1] * n
dist_k[k] = 0

def dfs(v):
    for u, du in to[v]:
        if dist_k[u] != -1:
            continue
        dist_k[u] = dist_k[v] + du
        dfs(u)
dfs(k)
dist_xky = [0] * q
for i in range(q):
    x, y = map(int, input().split())
    dist_xky[i] = dist_k[x] + dist_k[y]
print(*dist_xky, sep='\n')

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

def main():
	N = int(input())
	edge = [[] for _ in range(N)]
	for _ in range(N-1):
		a,b,d = map(int,input().split())
		edge[a-1].append((b-1,d))
		edge[b-1].append((a-1,d))
	
	Q,K = map(int,input().split())
	dist = [-1]*N
	dist[(K-1)] = 0
	q = [(0,K-1)]
	heapq.heapify(q)
	while q:
		_,now = heapq.heappop(q)
		for fol,d in edge[now]:
			if dist[fol] == -1:
				dist[fol] = dist[now]+d
				heapq.heappush(q,(dist[fol],fol))
	
	for _ in range(Q):
		a,b = map(int,input().split())
		print(dist[a-1]+dist[b-1])
	
if __name__ == "__main__":
	main()