Problem:
 Score : 400 points    Problem Statement You are given a tree with N vertices. Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices. The i -th edge (1≤i≤N-1) connects Vertices a_i and b_i , and has a length of c_i .  You are also given Q queries and an integer K . In the j -th query (1≤j≤Q) :   find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K .       Constraints  3≤N≤10^5   1≤a_i,b_i≤N (1≤i≤N-1)   1≤c_i≤10^9 (1≤i≤N-1)   The given graph is a tree.  1≤Q≤10^5   1≤K≤N   1≤x_j,y_j≤N (1≤j≤Q)   x_j≠y_j (1≤j≤Q)   x_j≠K,y_j≠K (1≤j≤Q)          Input Input is given from Standard Input in the following format:  N  a_1  b_1  c_1  :  a_{N-1}  b_{N-1}  c_{N-1}  Q  K  x_1  y_1  :  x_{Q}  y_{Q}       Output Print the responses to the queries in Q lines. In the j -th line j(1≤j≤Q) , print the response to the j -th query.        Sample Input 1 5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5      Sample Output 1 3
2
4  The shortest paths for the three queries are as follows:   Query 1 : Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3   Query 2 : Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2   Query 3 : Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4         Sample Input 2 7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7      Sample Output 2 5
14
22  The path for each query must pass Vertex K=2 .       Sample Input 3 10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10      Sample Output 3 17000000000

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

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

not_yet = deque(dist[k-1])
already = [False]*n
already[k-1] = True
for a, b, c in dist[k-1]:
  already[b] = True

while not_yet:
  key = not_yet.popleft()
  a, b, c = key[0], key[1], key[2]
  dist_k[b] = dist_k[a]+c
  
  for value in dist[b]:
    if already[value[1]]:
      continue
    not_yet.append(value)
    already[value[1]] = True

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

Solution (Python):

from collections import deque
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int,
          K: int, x: "List[int]", y: "List[int]"):
    G = [[] for _ in range(N)]
    for ai, bi, ci in zip(a, b, c):
        ai -= 1
        bi -= 1
        G[ai].append((bi, ci))
        G[bi].append((ai, ci))

    m = [-1] * N
    q = deque()
    K -= 1
    m[K] = 0
    q.append(K)
    while q:
        i = q.popleft()
        for j, cj in G[i]:
            if m[j] >= 0:
                continue
            m[j] = m[i] + cj
            q.append(j)

    for xi, yi in zip(x, y):
        xi -= 1
        yi -= 1
        print(m[xi] + m[yi])


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)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for _ in range(N)]
dis = [-1]*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
dis[K] = 0

def dfs(pos):
    for n_pos, n_cost in G[pos]:
        if dis[n_pos] != -1:
            continue
        dis[n_pos] = dis[pos]+n_cost
        dfs(n_pos)
dfs(K)

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

Solution (Python):
from collections import defaultdict,deque
def main():
    N = int(input())
    depth = [-1 for _ in range(N)]
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    stack = deque([K])
    depth[K] = 0
    while stack:
        v = stack.popleft()
        for e in tree[v]:
            u,c = e
            if u == K:
                continue
            if depth[u] == -1:
                stack.appendleft(u)
                depth[u] = depth[v] + c

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

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
edge = [tuple(map(int, input().split())) for _ in range(n-1)]

q, k = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(q)]

inf = 10 ** 18
connect = [{} for _ in range(n)]
for a, b, c in edge:
    connect[a-1][b-1] = c
    connect[b-1][a-1] = c

k -= 1

dis = [inf] * n
dis[k] = 0
search = {k}
ng = set()
while search:
    v = search.pop()
    for w, c in connect[v].items():
        if w not in ng:
            dis[w] = c + dis[v]
            search.add(w)
    ng.add(v)

for x, y in query:
    print(dis[x-1] + dis[y-1])

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

def d(tree, array, v):
  next_v = tree.get(v)
  
  for nv, nd in next_v:
    if array[nv] == -1:
      array[nv] = array[v] + nd
      d(tree, array, nv)
  

n = int(input())
tree = {}

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

array = [-1] * n
array[k] = 0

d(tree, array, k)

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

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


n = int(input())

GRAPH = [[] for _ in range(n + 1)]
EDGE = {}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a, b = min(a, b), max(a, b)
    GRAPH[a].append(b); GRAPH[b].append(a)
    EDGE[(a, b)] = c

def dfs(now, prev):
    for v in GRAPH[now]:
        if v == prev:
            continue
        next = v
        a, b = min(now, next), max(now, next)
        LENGTH[next] = LENGTH[now] + EDGE[(a, b)]
        dfs(next, now)

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

LENGTH = [0] * (n + 1)
dfs(k, 0)

for _ in range(q):
    x, y = map(int, input().split())
    print(LENGTH[x] + LENGTH[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):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import heapq
BIGDI = 10**18


n = inn()
dst = [{} for i in range(n+1)]
for i in range(n-1):
    u,v,a = inm()
    dst[u][v] = a
    dst[v][u] = a

qq,k = inm()

cost = [BIGDI]*(n+1)
q = [(0,k)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if cost[p]<=d:
        continue
    cost[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v], v))



for q in range(qq):
    x,y = inm()
    print(cost[x]+cost[y])

Solution (Python):
from collections import deque

def bfs(graph,root,distK):
    visited = set([root])       
    queue = deque([root]) 
    while queue:          
        vertex = queue.popleft()         
        for neighbour in graph[vertex]:  
            node = neighbour[0]
            dist = neighbour[1]
            if node not in visited:
                visited.add(node)
                queue.append(node)
                distK[node] = distK[vertex] + dist
    return distK

N = int(input())
graph = {i:[] for i in range(1,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())
distK = {K:0}
distK = bfs(graph,K,distK)
for _ in range(Q):
    x,y = map(int,input().split())
    print(distK[x] + distK[y])

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

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

def dfs(v, u, k):
    for i in d[v]:
        if i[0] == u:
            continue
        kkyori[i[0]] = k + i[1]
        dfs(i[0], v, k + i[1])

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

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

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from heapq import heappop, heappush

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N = INT()
abc = [LIST() for i in range(N-1)]
Q, K = MAP()
xy = [LIST() for i in range(Q)]

graph = defaultdict(list)

for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

    

d = dijkstra(graph, K-1)

for x, y in xy:
    
    
    
    ans = d[x-1] + d[y-1]
    
    print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from heapq import heappop, heappush

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N = INT()
abc = [LIST() for i in range(N-1)]
Q, K = MAP()
xy = [LIST() for i in range(Q)]

graph = defaultdict(list)

for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

    

d = dijkstra(graph, K-1)

for x, y in xy:
    
    
    
    ans = d[x-1] + d[y-1]
    
    print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
path = [LIST() for _ in range(N - 1)]
Q, K = MAP()
question = [LIST() for _ in range(Q)]

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

for i in range(N - 1):
	graph[path[i][0] - 1].append([path[i][1] - 1, path[i][2]])
	graph[path[i][1] - 1].append([path[i][0] - 1, path[i][2]])

depth = [0]*N

q = deque([K - 1])
connect = [0]*N
connect[K - 1] = 1
while q:
	n = q.popleft()
	for node, length in graph[n]:
		if connect[node] == 0:
			connect[node] = 1
			depth[node] = length + depth[n]
			q.append(node)

for i in range(Q):
	print(depth[question[i][0] - 1] + depth[question[i][1] - 1])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
l = [[] for _ in range(N)]
p = [0]*N
e = [0]*N
q = []

for _ in range(N-1):
    fi, si, wi = tuple(LIST())
    l[fi-1].append([si-1, wi])
    l[si-1].append([fi-1, wi])
Q, K = tuple(LIST())
for _ in range(Q):
    q.append(LIST())

def f(n, w):
    p[n] = 1
    e[n] = w
    for next_node in l[n]:
        nn, nw = tuple(next_node)
        if p[nn] == 0:
            f(nn, w+nw)
f(K-1, 0)
for nodes in q:
    fi, si = tuple(nodes)
    print(e[fi-1]+e[si-1])

Solution (Python):
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

for _ 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))


def dijkstra(s,n,g):
    
    
    d = [10**18] * n
    d[s] = 0
    q = [(0,s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in g[u]:  
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d




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

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

Solution (Python):
from heapq import heappop, heappush
n = int(input())
g = [[] for _ in range(n)]

for _ 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))


def dijkstra(s,n,g):
    
    
    d = [10**18] * n
    d[s] = 0
    q = [(0,s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in g[u]:  
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d




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

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

Solution (Python):
from heapq import heappop, heappush
n = int(input())
g = [[] for _ in range(n)]

for _ 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))


def dijkstra(s, n, edges):
    
    
    d = [10**18] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in edges[u]:
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


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

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

Solution (Python):
from collections import deque

def bfs(i):
    d[i] = 0
    q = deque()
    q.append(i)
    c = 1
    while True:
        if c == n:
            break
        p = q.popleft()
        c += 1
        h = G[p]
        for j in range(len(h)):
            if d[h[j]] == -1:
                q.append(h[j])
                v = w[p]
                d[h[j]] = d[p] + v[j]

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

q, k = map(int, input().split())
d = [-1] * n
bfs(k - 1)
for _ in range(q):
    x, y = map(int, input().split())
    print(d[x - 1] + d[y - 1])

Solution (Python):



import sys
sys.setrecursionlimit(10**9)

def main():
  n = int(input())
  inode2scores = [0] * (n+1)
  tree = [[] for _ in range(n+1)]
  weights = dict()
  for _ in range(n-1):
    a, b, c = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    weights[(a, b)] = weights[(b, a)] = c
    
  q, k = map(int, input().split())  
  visited = [False] * (n+1)
  iroot = k
  def dfs(inode, score=0):
    visited[inode] = True
    for ichild in tree[inode]:
      if visited[ichild]:
        continue
      inode2scores[ichild] = weights[(inode, ichild)] + score
      dfs(ichild, inode2scores[ichild])
  dfs(iroot)
  for _ in range(q):
    x, y = map(int, input().split())
    print(inode2scores[x] + inode2scores[y])

if __name__=='__main__':
  main()

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

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

vis = [False] * n
d = [-1] * n
def dfs(k, depth):
    vis[k] = True
    d[k] = depth
    for i in G[k]: 
        if not vis[i[0]]: dfs(i[0], depth + i[1])

q, k = map(int, input().split())
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

sys.setrecursionlimit(10 ** 7)

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

Q, K = map(int, input().split())
K -= 1
dist = [pow(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 _ in range(Q):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    print(dist[x] + dist[y])

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

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


def dfs(s):
	d = [-1] * n
	d[s] = 0
	stack = [s]

	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if d[v] == -1:
				d[v] = d[u] + c
				stack.append(v)

	return d


depths = dfs(k-1)

for x, y in xy:
	x -= 1
	y -= 1
	ans = depths[x] + depths[y]
	print(ans)

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


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v, w in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += w
                self.dfs(v)
                self.depth -= w

        self.colors[u] = self.BLACK


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

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

tree = Tree(adj)
tree.dfs(k-1)

for x, y in xy:
	x -= 1
	y -= 1
	ans = tree.depths[x] + tree.depths[y]
	print(ans)

Solution (Python):
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())
from collections import deque
dist=[-1]*(N+1)
dist[K]=0
q=deque()
q.append(K)

while len(q):
    p=q.popleft()
    for x,c in G[p]:
        if dist[x]!=-1:
            continue
        dist[x]=dist[p]+c
        q.append(x)

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

Solution (Python):
from collections import defaultdict, deque

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

distance_map = defaultdict(dict)

for a, b, c in ABC:
    distance_map[a][b] = c
    distance_map[b][a] = c

k_dist = {K: 0}

target = deque(distance_map[K].items())
while target:
    t, distance = target.pop()
    k_dist[t] = distance
    for v in map(lambda x: (x[0], x[1] + distance),filter(lambda x: x[0] not in k_dist, distance_map[t].items())):
        target.append(v)



for x,y in XY:
    print(k_dist[x]+k_dist[y])

Solution (Python):
n=int(input())
cd=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	cd[a-1].append([b,c])
	cd[b-1].append([a,c])
q,k=map(int,input().split())
from collections import deque
dis=[-1]*n
dis[k-1]=0
stack=deque([k])
while stack:
	p=stack.popleft()
	for i in range(len(cd[p-1])):
		if dis[cd[p-1][i][0]-1]==-1:
			dis[cd[p-1][i][0]-1]=dis[p-1]+cd[p-1][i][1]
			stack.append(cd[p-1][i][0])
for i in range(q):
	x,y=map(int,input().split())
	print(dis[x-1]+dis[y-1])

Solution (Python):
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d


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


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

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

for g in range(q):
    print(ans_list[g])

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """
    
    
    
    
    class Edge():
        
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        
        self.G = [[] for _ in range(V)] 
        self. _E = 0 
        self._V = V 
    
    
    def E(self):
        return self._E
    
    
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s,g):
        
        
        que = [] 
        d = [float("inf")] * self.V()
        prev = [None]*self.V() 
        d[s] = 0
        heapq.heappush(que,(0,s)) 
        
        while len(que)!=0:
            
            cost,v = heapq.heappop(que)
            
            
            if d[v] < cost:
                continue
                
            
            for i in range(len(self.G[v])):
                e = self.G[v][i] 
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost 
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) 
        
        
        path = []
        pos = g 
        for _ in range(self.V()+1):
            path.append(pos)
            if pos == s:
                break
            
            pos = prev[pos]
        path.reverse()
        
                    
        return d


def main():
    mod=10**9+7
    N=I()
    djk = Dijkstra(N)
    for _ in range(N-1):
        a,b,c=MI()
        djk.add2(a-1, b-1, c)
        
    Q,K=MI()
    d=djk.shortest_path(K-1,0)
    for _ in range(Q):
        x,y=MI()
        print(d[x-1]+d[y-1])

main()

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

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()) 
W = N - 1 

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

for i in range(W):
    x, y, z = [int(x) for x in input().split()]
    edge[x - 1].append([z, y - 1])
    edge[y - 1].append([z, x - 1])
Q, K = [int(x) for x in input().split()]

K_costs = dijkstra_heap(K - 1) 

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

Solution (Python):
from collections import deque
n=int(input())
A=[[0]*3 for i in range(n-1)]
B=[[[] for j in range(2)] for i in range(n)]
for i in range(n-1):
  A[i]=list(map(int,input().split()))
  B[A[i][0]-1][0].append(A[i][1]-1)
  B[A[i][0]-1][1].append(A[i][2])
  B[A[i][1]-1][0].append(A[i][0]-1)
  B[A[i][1]-1][1].append(A[i][2])
d=[0]*n
q,k=map(int,input().split())
C=deque([])
C.append(k-1)
E=[0]*n
E[k-1]=1
while len(C)>0:
  a=C[0]
  C.popleft()
  for i in range(len(B[a][0])):
    if E[B[a][0][i]]==0:
      C.append(B[a][0][i])
      d[B[a][0][i]]=d[a]+B[a][1][i]
      E[B[a][0][i]]=1
for i in range(q):
  s,t=map(int,input().split())
  print(d[s-1]+d[t-1])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

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

depth = [0] * N

def dfs(v, p, d):
    depth[v] = d
    for e in edges[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 -= 1
    y -= 1
    print(depth[x] + depth[y])

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)