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

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

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

q, k = map(int, input().split())
xy = []
for i in range(q):
    x, y = map(int, input().split())
    xy.append([x - 1, y - 1])
depth = [0 for _ in range(n)]
prev = [False for _ in range(n)]
depth[k - 1] = 0

import sys

sys.setrecursionlimit(10 ** 6)


def dfs(now, prev, cost, graph, depth):
    depth[now] = cost
    for k, v in graph[now].items():
        if k == prev:
            continue
        dfs(k, now, cost + v,  graph, depth)
    return depth


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

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

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

q, k = map(int, input().split())
xy = []
for i in range(q):
    x, y = map(int, input().split())
    xy.append([x - 1, y - 1])
depth = [0 for _ in range(n)]
prev = [False for _ in range(n)]
depth[k - 1] = 0

import sys

sys.setrecursionlimit(10 ** 6)


def dfs(now, prev, cost, graph, depth):
    depth[now] = cost
    for k, v in graph[now].items():
        if k == prev:
            continue
        dfs(k, now, cost + v,  graph, depth)
    return depth


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

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

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

q, k = map(int, input().split())
xy = []
for i in range(q):
    x, y = map(int, input().split())
    xy.append([x-1, y-1])
depth = [0 for _ in range(n)]
prev = [False for _ in range(n)]
depth[k-1] = 0

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(now, graph, depth, prev):
    if len(graph[now]) == 0 or prev[now]:
        return
    prev[now] = True
    for k, v in graph[now].items():
        if not prev[k]:
            depth[k] += depth[now] + v
            dfs(k, graph, depth, prev)
    return depth


depth = dfs(k-1, graph, depth, prev)
for x, y in xy:
    print(depth[x] + depth[y])

Solution (Python):

from collections import defaultdict,deque
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)]


graph = [defaultdict(int) for _ in range(N)]

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v):
    dist = [-1 for _ in range(N)]
    dist[v] = 0
    que = deque()
    que.append(v)
    while len(que) > 0:
        i = que.pop()  
        
        for n, val in graph[i].items():
            if dist[n] == -1:
                dist[n] = dist[i] + val
                que.append(n)
    return dist

dist = xfs(K-1)

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

Solution (Python):
n = int(input())
d = []
for i in range(n - 1):
    d.append([int(m) for m in input().split()])
q, k = map(int, input().split())
z = []
for i in range(q):
    z.append([int(m) for m in input().split()])

for i in range(n - 1):
    d[i][0] -= 1
    d[i][1] -= 1
for i in range(q):
    z[i][0] -= 1
    z[i][1] -= 1
def BFS(k, edges, N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(k)
  dist[k]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist

root = BFS(k - 1, d, n)

for i in range(q):
    print(root[z[i][0]] + root[z[i][1]])

Solution (Python):
import heapq
from collections import defaultdict

N = int(input())

graph = defaultdict(list)

for i in range(N - 1):
	a, b, w = list(map(int, input().split()))
	graph[a - 1].append([b - 1, w])
	graph[b - 1].append([a - 1, w])


dist_node = [float("inf") for i in range(N)]
ques, s = list(map(int, input().split()))
s = s - 1
dist_node[s] = 0


Q = []
heapq.heappush(Q, (dist_node[s], s)) 

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node[v] < dis:
		continue
	for u, w in graph[v]:
		alt = dis + w
		if dist_node[u] > alt:
			dist_node[u] = alt
			heapq.heappush(Q, (alt, u))


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

Solution (Python):

inf = 10**16
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append((b,c))
    edge[b].append((a,c))

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

d = [inf for _ in range(n)]
d[k] = 0
stack = [k]
while len(stack)>0:
    v = stack.pop()
    for u,c in edge[v]:
        if d[u]==inf:
            d[u] = d[v]+c
            stack.append(u)

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

for c in res:
    print(c)

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

n=int(input())
m=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int, input().split())
    m[a-1].append([b-1,c])
    m[b-1].append([a-1,c])
q,k=map(int, input().split())
    
def reach(m,d,k):
    for i in m[k]:
        if d[i[0]]==-1:
            d[i[0]]=d[k]+i[1]
            reach(m,d,i[0])
d=[-1]*n
d[k-1]=0
reach(m,d,k-1)

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

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

def make_Graph(N, edges):
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    dd = [float("inf")] * N
    Q.append(start)
    dd[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

N = int(input())

sys.setrecursionlimit(100)

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

Q, K =(int(i) for i in input().split())
dd = [0] * N

try:
    DFS(N, graph, K-1, -1, 0)
except:
    dd = BFS(N, graph, K-1)

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

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

def make_Graph(N, edges):
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    dd = [float("inf")] * N
    Q.append(start)
    dd[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

N = int(input())

sys.setrecursionlimit(1000000)

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

Q, K =(int(i) for i in input().split())
dd = [0] * N

DFS(N, graph, K-1, -1, 0)

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

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

def make_Graph(N, edges):
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    dd = [float("inf")] * N
    Q.append(start)
    dd[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

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

Q, K =(int(i) for i in input().split())
dd = [0] * N

try:
    DFS(N, graph, K-1, -1, 0)
except:
    dd = BFS(N, graph, K-1)

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

Solution (Python):
n=int(input())
ro=[{}for i in range(n)]
dis=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    ro[a-1][b-1]=c
    ro[b-1][a-1]=c
q,k=map(int,input().split())
dis[k-1]=0
stack=[k-1]
while stack:
    s=stack.pop()
    for i,j in ro[s].items():
        if dis[i] == -1:
            dis[i]=dis[s]+j
            stack.append(i)
for i in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(dis[x]+dis[y])

Solution (Python):
N=int(input())
Tree=[{} for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Tree[a-1][b-1]=c
  Tree[b-1][a-1]=c
Q,K=map(int,input().split())
depth=[-1]*N
depth[K-1]=0
dfs_stack=[K-1]
while dfs_stack:
  s=dfs_stack.pop()
  for t,t_depth in Tree[s].items():
    if depth[t]==-1:
      depth[t]=depth[s]+t_depth
      dfs_stack.append(t)
      
for q in range(Q):
  x,y=map(int,input().split())
  print(depth[x-1]+depth[y-1])

Solution (Python):
import sys

sys.setrecursionlimit(10000000)


V=int(input().strip())
E=V-1
inf=3*10**15
G=[]
dist=[inf]*V

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1])

visited=[False]*V
def dfs(v,p,d):
    
    dist[v]=d
    for q in G[v]:
        if q[1]==p:
            continue
        dfs(q[1],v,d+q[0])

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

dfs(K,-1,0)

x=[]
y=[]

for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)
    y.append(yt-1)
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Solution (Python):
import sys
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path


input = sys.stdin.readline
N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))


L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])

Solution (Python):
import heapq
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b,c in src:
    es[a-1].append((b-1,c))
    es[b-1].append((a-1,c))

Q,K = map(int,input().split())
qs = [tuple(map(int,input().split())) for i in range(Q)]
K -= 1

INF = float('inf')
dists = [INF]*N
dists[K] = 0
hq = [(0,K)]
heapq.heapify(hq)

while hq:
    d,v = heapq.heappop(hq)
    for to,c in es[v]:
        if d+c >= dists[to]: continue
        dists[to] = d+c
        heapq.heappush(hq, (d+c, to))

for a,b in qs:
    print(dists[a-1] + dists[b-1])

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

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

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

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

dist = dijkstra(graph,n,k-1)

xy = [tuple(li_()) for _ in range(q)]

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

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

N = int(input())
X, Y = [], []

tree = {key+1: [] for key in range(N)}  



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





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

cost = {}  


def dfs(v, p, d):
    """
    深さ優先探索
    再帰的に処理する
    args:
        v: 現在の頂点
        p: vの親(訪問元)
        d: 現在の距離
    """
    cost[v] = d
    for i, co in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + co)


dfs(K, -1, 0)


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

for a in ans:
    print(a)

Solution (Python):
from collections import deque

n = int(input())
path = {}
for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    if not a in path.keys():
        path[a] = [(b, c)]
    else:
        path[a].append((b, c))
    if not b in path.keys():
        path[b] = [(a, c)]
    else:
        path[b].append((a, c))
q, k = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(q)]

dist = [None]*(n+1)
dist[k] = 0
que = deque([(k, 0)])
while len(que) > 0:
    node, d = que.popleft()
    dist[node] = d
    for node_next, d_next in path[node]:
        if dist[node_next] is None:
            que.append((node_next, d+d_next))


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

Solution (Python):
from collections import deque
 
n = int(input())
path = {}
for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    if not a in path.keys():
        path[a] = [(b, c)]
    else:
        path[a].append((b, c))
        
    if not b in path.keys():
        path[b] = [(a, c)]
    else:
        path[b].append((a, c))
q, k = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(q)]

dist = [None]*(n+1)
dist[k] = 0
que = deque([(k, 0)])
while len(que) > 0:
    node, d = que.popleft()
    dist[node] = d
    for node_next, d_next in path[node]:
        if dist[node_next] is None:
            que.append((node_next, d+d_next))

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

Solution (Python):
N = int(input())
route = [{} for _ in range(N)]
dist = [-1] * N
for i in range(N - 1):
    a, b, d = map(int, input().split())
    route[a-1][b-1] = d
    route[b-1][a-1] = d

Q, K = map(int, input().split())
dist[K-1] = 0
dfs_stack = [K-1]
while dfs_stack:
    s = dfs_stack.pop()
    for t, t_dist in route[s].items():
        if dist[t] == -1:
            dist[t] = dist[s] + t_dist
            dfs_stack.append(t)
for i in range(Q):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    print(dist[x] + dist[y])

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

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


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


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

Solution (Python):
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

ctr = 1
Q, K = inpl()
now = {K}
dist = [0 for _ in range(N+1)]
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            dist[nb] = dist[na] + nc
            path[nb].remove((na,nc))
            now.add(nb)
            ctr += 1
    if ctr >=  N:
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])

Solution (Python):
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

ctr = 1
Q, K = inpl()
now = [K]
dist = [0 for _ in range(N+1)]
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            dist[nb] = dist[na] + nc
            path[nb].remove((na,nc))
            now.append(nb)
            ctr += 1
    if ctr >=  N:
        break
for i in range(Q):
    x, y = inpl()
    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)]

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

depth=[0 for _ in range(n)]
from collections import deque
que=deque([])
v,p,d=k-1,-1,0
que.append((v,p,d))
while que:
    v,p,d=que.pop()
    depth[v]=d
    for t in z[v]:
        if t[0]==p:
            continue
        que.append((t[0],v,d+t[1]))
for x,y in xy:
    print(depth[x-1]+depth[y-1])

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

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    

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

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

C = [float("inf") for _ in range(N)]
V = [False for _ in range(N)]
C[K-1] = 0
H = [(0, K-1)] 
heapq.heapify(H)
while H:
    cost, node = heapq.heappop(H)
    V[node] = True
    for n in P[node]:
        if V[n[1]] == False:
            if n[0] + cost < C[n[1]]:
                C[n[1]] = n[0] + cost
                heapq.heappush(H, (n[0] + cost, n[1]))
Ans = []
for i in range(Q):
    x, y = map(int, input().split())
    Ans.append(C[x-1]+C[y-1])
for i in range(Q):
    print(Ans[i])

Solution (Python):
from heapq import heappush, heappop
from collections import deque
N = int(input())
G = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append((b, c))
    G[b].append((a, c))

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

INF = float("inf")
d = [INF] * N
d[K] = 0
que = [(0, K)]
while que:
    cost, v = heappop(que)
    if d[v] < cost:
        continue
    for w, c in G[v]:
        if d[v] + c < d[w]:
            d[w] = d[v] + c
            heappush(que, (d[w], w))

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

Solution (Python):
N = int(input())
edge = [{} for _ in range(N + 1)]
dist = [-1] * (N + 1)
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    edge[a][b] = c
    edge[b][a] = c

Q, K = map(int, input().split())
dist[K] = 0
dfs_stack = [K]
while dfs_stack:
    s = dfs_stack.pop()
    for t, t_dist in edge[s].items():
        if dist[t] == -1:
            dist[t] = dist[s] + t_dist
            dfs_stack.append(t)

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

Solution (Python):
N = int(input())
edge = [{} for _ in range(N + 1)]
dist = [-1] * (N + 1)
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    edge[a][b] = c
    edge[b][a] = c

Q, K = map(int, input().split())
dist[K] = 0
dfs_stack = [K]
while dfs_stack:
    s = dfs_stack.pop()
    for t, t_dist in edge[s].items():
        if dist[t] == -1:
            dist[t] = dist[s] + t_dist
            dfs_stack.append(t)

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

Solution (Python):
N = int(input())
edge = [{} for _ in range(N + 1)]
dist = [-1] * (N + 1)
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    edge[a][b] = c
    edge[b][a] = c

Q, K = map(int, input().split())
dist[K] = 0
dfs_stack = [(K, 0)]
while dfs_stack:
    s, s_dist = dfs_stack.pop()
    for t, t_dist in edge[s].items():
        if dist[t] == -1:
            dist[t] = s_dist + t_dist
            dfs_stack.append((t, dist[t]))

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

Solution (Python):
import heapq

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

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


distance = [10**15]*(n+1)
distance[k] = 0
h = []
heapq.heappush(h,[0,k])
while h:
    dist, node = heapq.heappop(h)
    for ndist, nnode in adj[node]:
        if distance[nnode] > distance[node] + ndist:
            distance[nnode] = distance[node] + ndist
            heapq.heappush(h, [distance[nnode],nnode])


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

Solution (Python):
import heapq

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

INF = float('inf')
dist = [INF for i in range(n)]
dist[k-1] = 0
hq = [(0, k-1)]
while hq:
    cost, node = heapq.heappop(hq)

    
    
    if cost > dist[node]:
        continue

    for n_node, n_cost in g[node]:
        d = dist[node] + n_cost
        if d < dist[n_node]:
            dist[n_node] = d
            heapq.heappush(hq, (dist[n_node], n_node))

for i in range(q):
    print(dist[qs[i][0]-1] + dist[qs[i][1]-1])

Solution (Python):
import heapq

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

INF = float('inf')
dist = [INF for i in range(n)]
dist[k-1] = 0
hq = [(0, k-1)]
while hq:
    cost, node = heapq.heappop(hq)
    if cost > dist[node]:
        continue
    for n_node, n_cost in g[node]:
        d = dist[node] + n_cost
        if d < dist[n_node]:
            dist[n_node] = d
            heapq.heappush(hq, (dist[n_node], n_node))

for i in range(q):
    print(dist[qs[i][0]-1] + dist[qs[i][1]-1])

Solution (Python):
import heapq

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

INF = float('inf')
dist = [INF for i in range(n)]
dist[k-1] = 0
hq = [(0, k-1)]
while hq:
    cost, node = heapq.heappop(hq)
    for n_node, n_cost in g[node]:
        d = dist[node] + n_cost
        if d < dist[n_node]:
            dist[n_node] = d
            heapq.heappush(hq, (dist[n_node], n_node))

for i in range(q):
    print(dist[qs[i][0]-1] + dist[qs[i][1]-1])

Solution (Python):
import heapq

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

INF = float('inf')
dist = [INF for i in range(n)]
dist[k-1] = 0
hq = [(0, k-1)]
heapq.heapify(hq)
while hq:
    cost, node = heapq.heappop(hq)
    for n_node, n_cost in g[node]:
        d = dist[node] + n_cost
        if d < dist[n_node]:
            dist[n_node] = d
            heapq.heappush(hq, (dist[n_node], n_node))

for i in range(q):
    print(dist[qs[i][0]-1] + dist[qs[i][1]-1])

Solution (Python):
import heapq

n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))
q, k = map(int, input().split())
x = []
y = []
for i in range(q):
    X, Y = map(int, input().split())
    x.append(X)
    y.append(Y)

dist = [10**15 for i in range(n)]
h = []
heapq.heappush(h, (0, k-1))
while len(h) > 0:
    top = heapq.heappop(h)
    for i in g[top[1]]:
        d = top[0] + i[1]
        if dist[i[0]] > d:
            dist[i[0]] = d
            heapq.heappush(h, (d, i[0]))

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

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

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

n = ni()
abc = []
for _ in range(n-1):
    a,b,c = li()
    a -= 1
    b -= 1
    abc.append((a,b,c))
q,k = li()
k -= 1
query = [li_() for _ in range(q)]


graph = [[] for _ in range(n)]
for frm,to,cost in abc:
    graph[frm].append((cost,to))
    graph[to].append((cost,frm))


dist = dijkstra(graph, n, k)


for frm,to in query:
    print(dist[frm] + dist[to])

Solution (Python):
import heapq
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]
Q,K = map(int,input().split())
K -= 1
qs = [tuple(map(int,input().split())) for i in range(Q)]

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

INF = float('inf')
dists = [INF] * N
dists[K] = 0
hq = [(0,K)]
heapq.heapify(hq)

while hq:
    dist,v = heapq.heappop(hq)
    dists[v] = dist
    for dd,to in es[v]:
        if dists[to] != INF: continue
        heapq.heappush(hq, (dist+dd, to))

for a,b in qs:
    a,b = a-1,b-1
    print(dists[a] + dists[b])

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

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

n = ni()
abc = []
for _ in range(n-1):
    a,b,c = li()
    a -= 1
    b -= 1
    abc.append((a,b,c))
q,k = li()
k -= 1
query = [li_() for _ in range(q)]


graph = [[] for _ in range(n)]
for frm,to,cost in abc:
    graph[frm].append((cost,to))
    graph[to].append((cost,frm))


dist = dijkstra(graph, n, k)


for frm,to in query:
    print(dist[frm] + dist[to])

Solution (Python):
from collections import deque
def dfs(neigh,K):
    q = deque([K])
    d = [0]*N
    visited = [0]*N
    visited[K] = True
    while q:
        p = q.pop()
        for di,cost in neigh[p]:
            if visited[di]:
                continue
            d[di] = d[p]+cost
            visited[di] = True
            q.append(di)
    return d

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

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