CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
l = [list(map(int,input().split())) for _ in range(n-1)]

dp = [[0 for _ in range(n)] for _ in range(n)]
INF = 10**18
for i in range(n):
    for j in range(n):
        if i!=j:
            dp[i][j] = INF
for a,b,c in l:
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
#print(dp)

#最短リスト
for c in range(n):
    for f in range(n):
        for la in range(n):
            dp[f][la] = min(dp[f][la] , dp[f][c] +  dp[c][la])

q,k = list(map(int,input().split()))
for _ in range(q):
    x,y = list(map(int,input().split()))
    k1 = dp[x-1][k-1] + dp[k-1][y-1]
    k2 = dp[y-1][k-1] + dp[k-1][x-1]
    print((min(k1,k2)))


# Optimized solution
import sys

sys.setrecursionlimit(200000)

n = int(eval(input()))
l = [list(map(int,input().split())) for _ in range(n-1)]
q,k = list(map(int,input().split()))
k -= 1
#kからの距離
tree = [[] for _ in range(n)]
for a,b,c in l:
    a -= 1
    b -= 1
    tree[a].append([b,c])
    tree[b].append([a,c])

bit = [0 for _ in range(n)]
depth = [0 for _ in range(n)]
def dfs(v,d=0):
    bit[v] = 1
    depth[v] = d
    for j,k in tree[v]:
        if bit[j]==0:
            dfs(j,d+k)
dfs(k)

for _ in range(q):
    x,y = list(map(int,input().split()))
    x-= 1
    y-= 1
    print((depth[x] + depth[y]))
# Original solution
N = int(eval(input()))
edge = set(tuple(map(int, input().split())) for i in range(N-1))
Q, K = list(map(int, input().split()))
query = [tuple(map(int, input().split())) for i in range(Q)]

# dist[-i]:頂点Kから頂点iまでの距離
dist = [None for i in range(N)]
dist[-K] = 0
while edge:
    rm = set()
    for a, b, c in edge:
        if dist[-a] is not None:
            dist[-b] = dist[-a] + c
            rm.add((a, b, c))
        elif dist[-b] is not None:
            dist[-a] = dist[-b] + c
            rm.add((a, b, c))
    edge -= rm

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


# Optimized solution
import sys
sys.setrecursionlimit(1000000)

N = int(eval(input()))

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

Q, K = list(map(int, input().split()))
query = [tuple(map(int, input().split())) for i in range(Q)]

# dist[-i]:頂点Kから頂点iまでの距離
dist = [0 for i in range(N)]

def dfs(v, prv, ds):
    dist[-v] = ds
    for nxt, c in adj[-v]:
        if nxt != prv:
            dfs(nxt, v, ds + c)

dfs(K, None, 0)

for x, y in query:
    print((dist[-x] + dist[-y]))
# Original solution
import collections
N = int(eval(input()))
List = [[] for _ in range(N)]
ans = [-1]*N
for i in range(N-1):
    a, b, c = list(map(int, input().split()))
    List[a-1].append((b-1, c))
    List[b-1].append((a-1, c))
Q, K = list(map(int, input().split()))
queue = collections.deque([K-1])
ans[K-1] = 0
while queue:
    edge = queue.pop()
    for node in List[edge]:
        index, cost = node
        if ans[index]>0:
            continue
        ans[index] = ans[edge]+cost
        queue.append(index)
for i in range(Q):
    x, y = list(map(int, input().split()))
    print((ans[x-1]+ans[y-1]))

# Optimized solution
import sys
input = sys.stdin.readline
N = int(eval(input()))
List = [[] for _ in range(N)]
ans = [-1]*N
for i in range(N-1):
    a, b, c = list(map(int, input().split()))
    List[a-1].append((b-1, c))
    List[b-1].append((a-1, c))
Q, K = list(map(int, input().split()))
queue = [K-1]
ans[K-1] = 0
while queue:
    edge = queue.pop()
    for node in List[edge]:
        index, cost = node
        if ans[index]>0:
            continue
        ans[index] = ans[edge]+cost
        queue.append(index)
for i in range(Q):
    x, y = list(map(int, input().split()))
    print((ans[x-1]+ans[y-1]))
# Original solution
import sys
sys.setrecursionlimit(10**6)

def dfs(v, d=0):
    seen[v] = True
    dist[v] = d

    for i in graph[v]:
        next_v = i[0]
        l = i[1]
        if seen[next_v] == True:
            continue
        dfs(next_v, d+l)

    return

N = int(eval(input()))

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

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

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

for i in range(Q):
    ans = 0
    x, y = list(map(int, input().split()))

    seen = [False for i in range(N + 1)]
    dist = [0 for i in range(N + 1)]
    dfs(x)
    ans += dist[K]

    seen = [False for i in range(N + 1)]
    dist = [0 for i in range(N + 1)]
    dfs(K)
    ans += dist[y]
    
    print(ans)

# Optimized solution
import sys
sys.setrecursionlimit(10**6)

def dfs(v, d=0):
    seen[v] = True
    dist[v] = d

    for i in graph[v]:
        next_v = i[0]
        l = i[1]
        if seen[next_v] == True:
            continue
        dfs(next_v, d+l)

    return

N = int(eval(input()))

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

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

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

seen = [False for i in range(N + 1)]
dist = [0 for i in range(N + 1)]
dfs(K)

for i in range(Q):
    x, y = list(map(int, input().split()))
    print((dist[x] + dist[y]))
# Original solution
from collections import deque
N = int(eval(input()))
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = list(map(int, input().split()))
    edge[a].append([b, c])
    edge[b].append([a, c])


def BFS(x, y):
    visited = [False for _ in range(N+1)]
    next_N = [False for _ in range(N+1)]
    INF = float('inf')
    dest = [INF for _ in range(N+1)]
    d = deque()
    visited[x] = True
    dest[x] = 0
    for B, C in edge[x]:
        d.append([B, C])
        next_N[B] = True
        dest[B] = dest[x] + C
    while d:
        now = d.popleft()
        visited[now[0]] = True
        for B, C in edge[now[0]]:
            if visited[B] == False and next_N[B] == False:
                d.append([B, C])
                next_N[B] = True
                dest[B] = dest[now[0]] + C
    return dest[y]

Q, K = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(Q)]
for X, Y in xy:
    print((BFS(X, K) + BFS(K, Y)))


# Optimized solution
from collections import deque
N = int(eval(input()))
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = list(map(int, input().split()))
    edge[a].append([b, c])
    edge[b].append([a, c])


def BFS(x):
    visited = [False for _ in range(N+1)]
    next_N = [False for _ in range(N+1)]
    INF = float('inf')
    dest = [INF for _ in range(N+1)]
    d = deque()
    visited[x] = True
    dest[x] = 0
    for B, C in edge[x]:
        d.append([B, C])
        next_N[B] = True
        dest[B] = dest[x] + C
    while d:
        now = d.popleft()
        visited[now[0]] = True
        for B, C in edge[now[0]]:
            if visited[B] == False and next_N[B] == False:
                d.append([B, C])
                next_N[B] = True
                dest[B] = dest[now[0]] + C
    return dest

Q, K = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(Q)]
DEST = BFS(K)
for X, Y in xy:
    print((DEST[X] + DEST[Y]))
# Original solution
import queue
def main():
    n = int(eval(input()))
    a = []
    b = []
    c = []
    lst = [[] for _ in range(n)]

    for i in range(n - 1):
        aa, bb, cc = list(map(int,input().split()))
        lst[aa - 1].append((bb - 1, cc))
        lst[bb - 1].append((aa - 1, cc))

    q, k = list(map(int,input().split()))
    x = []
    y = []
    for i in range(q):
        xx, yy = list(map(int,input().split()))
        x.append(xx - 1)
        y.append(yy - 1)
    qq = queue.Queue()
    qq.put(k - 1)
    dist = [0] * n
    while not qq.empty():
        now = qq.get()
        for to, w in lst[now]:
            if dist[to] != 0:
                continue
            dist[to] = dist[now] + w
            qq.put(to)

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





if __name__ == '__main__':
    main()


# Optimized solution
from collections import deque
def main():
    n = int(eval(input()))
    a = []
    b = []
    c = []
    lst = [[] for _ in range(n)]

    for i in range(n - 1):
        aa, bb, cc = list(map(int,input().split()))
        lst[aa - 1].append((bb - 1, cc))
        lst[bb - 1].append((aa - 1, cc))

    q, k = list(map(int,input().split()))
    x = []
    y = []
    for i in range(q):
        xx, yy = list(map(int,input().split()))
        x.append(xx - 1)
        y.append(yy - 1)
    qq = deque()
    qq.append(k - 1)
    dist = [0] * n
    while len(qq) != 0:
        now = qq.popleft()
        for to, w in lst[now]:
            if dist[to] != 0:
                continue
            dist[to] = dist[now] + w
            qq.append(to)

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





if __name__ == '__main__':
    main()
# Original solution
from collections import defaultdict

N = int(eval(input()))
E = defaultdict(list)
W = dict()

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

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

costs = [float('inf')]*(N+1)
costs[K] = 0

stack = [K]

while stack:
  s = stack.pop()
  for t in E[s]:
    if costs[t] > costs[s] + W[(s,t)]:
      costs[t] = costs[s] + W[(s,t)]
      stack.append(t)

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

# Optimized solution

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

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

Q,K = list(map(int,input().split()))
K -= 1
costs = [None]*N
costs[K] = 0

stack = [K]

while stack:
  s = stack.pop()
  c = costs[s]
  for t,d in E[s]:
    if costs[t] is None:
      costs[t] = c + d
      stack.append(t)

for i in range(Q):
  x,y = list(map(int,input().split()))
  print((costs[x-1]+costs[y-1]))
# Original solution
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(eval(input()))

lines = defaultdict(set)

for i in range(N-1):
	a,b,c = inpl() #a -> b コスト:c の経路
	lines[a].add((b,c))
	lines[b].add((a,c))

Q,s = inpl()

weight = [-1]*(N+1)
weight[s] = 0

q = [[0,s]]
heapq.heapify(q)

while q:
	w0,s = heapq.heappop(q)
	for line in list(lines[s]):
		t = line[0]
		w = w0 + line[1]
		if weight[t] == -1 or weight[t] > w: #未探索orより小さい
			heapq.heappush(q, [w,t])
			weight[t] = w

for i in range(Q):
	x,y = inpl()
	print((weight[x]+weight[y]))


# Optimized solution
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(eval(input()))

lines = defaultdict(set)
for i in range(N-1):
	a,b,c = inpl()
	a -= 1
	b -= 1
	lines[a].add((b,c))
	lines[b].add((a,c))

Q,s = inpl()
s -= 1
ss = [-1]*N
ss[s] = 0

def check(a,w):
	global ss
	for b,c in lines[a]:
		if ss[b] == -1:
			ss[b] = w + c
			check(b,w+c)

check(s,0)

for i in range(Q):
	x,y = inpl()
	print((ss[x-1]+ss[y-1]))
# Original solution
from collections import deque

N=int(eval(input()))
cost=[[float("inf")]*N for _ in range(N)]
graph=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=list(map(int,input().split()))
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
    cost[a][b]=c
    cost[b][a]=c

def dfs(start):
    visited=[False]*N
    queue=deque([start])
    visited[start]=0
    while queue:
        x=queue.pop()
        for y in graph[x]:
            if visited[y]!=False:
                continue
            visited[y]=visited[x]+cost[x][y]
            queue.append(y)
    return visited

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

# Optimized solution
import sys
sys.setrecursionlimit(10**9)

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

def dfs(start):
    for x,cost in graph[start]:
        if d[x]==-1:
            d[x]=d[start]+cost
            dfs(x)

Q,K=list(map(int,input().split()))
K-=1
d=[-1]*N
d[K]=0
dfs(K)
for i in range(Q):
    x,y=list(map(int,input().split()))
    x-=1
    y-=1
    print((d[x]+d[y]))
# Original solution
from queue import deque

n = int(eval(input()))
edges = [set() for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = list(map(int, input().split()))
    edges[a].add((c, b))
    edges[b].add((c, a))
q, k = list(map(int, input().split()))
stack = deque([(0, k)])
costs = [0] * (n + 1)
visited = set()
while stack:
    c, p = stack.popleft()
    costs[p] = c
    visited.add(p)
    stack.extend((c + c2, p2) for c2, p2 in edges[p] if p2 not in visited)

ans = []
for _ in range(q):
    x, y = list(map(int, input().split()))
    ans.append(costs[x] + costs[y])
print(('\n'.join(map(str, ans))))


# Optimized solution
n = int(eval(input()))
edges = [set() for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = list(map(int, input().split()))
    edges[a].add((c, b))
    edges[b].add((c, a))
q, k = list(map(int, input().split()))
stack = [(0, k, None)]
costs = [0] * (n + 1)
visited = set()
while stack:
    c, p, a = stack.pop()
    costs[p] = c
    visited.add(p)
    stack.extend((c + c2, p2, p) for c2, p2 in edges[p] if p2 != a)

print(('\n'.join(map(str, (costs[x] + costs[y] for x, y
                          in (list(map(int, input().split())) for _ in range(q)))))))
# Original solution
n = int(eval(input()))
edges = [set() for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = list(map(int, input().split()))
    edges[a].add((c, b))
    edges[b].add((c, a))
q, k = list(map(int, input().split()))
stack = [(0, k, None)]
costs = [0] * (n + 1)
while stack:
    c, p, a = stack.pop()
    costs[p] = c
    stack.extend((c + c2, p2, p) for c2, p2 in edges[p] if p2 != a)

print(('\n'.join(map(str, (costs[x] + costs[y] for x, y
                          in (list(map(int, input().split())) for _ in range(q)))))))


# Optimized solution
n = int(eval(input()))
edges = [[] for _ in range(n + 1)]
for a, b, c in (list(map(int, input().split())) for _ in range(n - 1)):
    edges[a].append((c, b))
    edges[b].append((c, a))
q, k = list(map(int, input().split()))
stack = [(0, k, None)]
costs = [0] * (n + 1)
while stack:
    c, p, a = stack.pop()
    costs[p] = c
    stack.extend((c + c2, p2, p) for c2, p2 in edges[p] if p2 != a)
print(('\n'.join(map(str, (costs[x] + costs[y] for x, y in (list(map(int, input().split())) for _ in range(q)))))))
# Original solution
import heapq

N = int(eval(input()))
nb = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    nb[a].append((c, b))
    nb[b].append((c, a))
for x in nb:
    x.sort()

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

dist = [2 ** 62] * N
visited = set()
h = [(0, K, -1)]
while h:
    d0, node, parent = heapq.heappop(h)
    if node in visited:
        continue
    visited.add(node)
    dist[node] = d0
    for d1, child in nb[node]:
        if child != parent and d0 + d1 < dist[child]:
            heapq.heappush(h, (d0 + d1, child, node))

for i in range(Q):
    x, y = list(map(int, input().split()))
    # print(f"{x}->K = {dist[x]}, K->{y} = {dist[y]}")
    print((dist[x - 1] + dist[y - 1]))


# Optimized solution
import sys
import heapq

input = sys.stdin.readline


def main():

    N = int(eval(input()))
    nb = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        nb[a].append((c, b))
        nb[b].append((c, a))
    for x in nb:
        x.sort()

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

    dist = [2 ** 62] * N
    h = [(0, K, -1)]
    while h:
        d0, node, parent = heapq.heappop(h)
        if d0 >= dist[node]:
            continue
        dist[node] = d0
        for d1, child in nb[node]:
            if child != parent and d0 + d1 < dist[child]:
                heapq.heappush(h, (d0 + d1, child, node))

    for i in range(Q):
        x, y = list(map(int, input().split()))
        # print(f"{x}->K = {dist[x]}, K->{y} = {dist[y]}")
        print((dist[x - 1] + dist[y - 1]))


if __name__ == "__main__":
    main()
# Original solution
from heapq import heappop, heappush

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

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

d = [float('inf')] * (N + 1)
d[K] = 0
#prev = [None] * (N + 1)
q = [(0, K)]
while q:
    _, u = heappop(q)
    for v, c in links[u]:
        alt = d[u] + c
        if d[v] > alt:
            d[v] = alt
            #prev[v] = u
            heappush(q, (alt, v))

result = []
for _ in range(Q):
    x, y = list(map(int, input().split()))
    result.append(d[x] + d[y])
print(('\n'.join(str(v) for v in result)))


# Optimized solution
N = int(eval(input()))
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    links[a].append((b, c))
    links[b].append((a, c))

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

d = [float('inf')] * (N + 1)
d[K] = 0
q = [K]
while q:
    i = q.pop()
    for j, c in links[i]:
        if d[i] + c < d[j]:
            d[j] = d[i] + c
            q.append(j)

result = []
for _ in range(Q):
    x, y = list(map(int, input().split()))
    result.append(d[x] + d[y])
print(('\n'.join(str(v) for v in result)))
# Original solution
from collections import defaultdict

def warshall_floyd(V, E):
    INF = 10 ** 10
    d = [defaultdict(lambda: INF) for i in range(V)]
    for i, j, c in E:
        d[i - 1][j - 1] = c
        d[j - 1][i - 1] = c
    for k in range(V):
        for i in range(V - 1):
            for j in range(i, V):
                dk = d[i][k] + d[k][j]
                if d[i][j] > dk:
                    d[i][j] = dk
                    d[j][i] = dk
    return d

N = int(eval(input()))
E = [list(map(int, input().split())) for _ in range(N - 1)]
d = warshall_floyd(N, E)

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


# Optimized solution
def dfs(i, V, E):
    S = [i]
    while(len(S) > 0):
        vi = S.pop()
        d = V[vi]
        for j, value in list(E[vi].items()):
            if V[j] > value + d:
                V[j] = value + d
                S.append(j)
    return V

INF = 10 ** 14
n = int(eval(input()))
V = [INF for _ in range(n + 1)]
E = [{} for _ in range(n + 1)]
for i in range(n - 1):
    ai, bi, ci = list(map(int, input().split()))
    E[ai][bi] = ci
    E[bi][ai] = ci

q, k = list(map(int, input().split()))
z = [list(map(int, input().split())) for _ in range(q)]
V[k] = 0

V = dfs(k, V, E)
for i in range(q):
    x, y = z[i]
    print((V[x] + V[y]))
# Original solution
from collections import *
d=defaultdict(list)
n=int(eval(input()))

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

#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})
 
def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in list(d.keys())}
    preference= {node:None         for node in list(d.keys())}#最適路のこと 
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while True:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        if len(Q)==0:
            break #全部の点消したら終了
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

q,k=list(map(int,input().split()))
x,y=DIJKSTRA(k,d)

for i in range(q):
    a,b=list(map(int,input().split()))
    print((y[a]+y[b]))


# Optimized solution
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

d=defaultdict(list)
n=int(eval(input()))

for s in range(n-1):
    a,b,c=list(map(int,input().split()))
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in list(d.keys())}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

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

for i in range(q):
    a,b=list(map(int,input().split()))
    print((y[a]+y[b]))
# Original solution
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(eval(input()))
 
for s in range(n-1):
    a,b,c=list(map(int,input().split()))
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})
 
def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in list(d.keys())}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=list(map(int,input().split()))
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=list(map(int,input().split()))
    print((y[a]+y[b]))

# Optimized solution
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(eval(input()))
 
for s in range(n-1):
    a,b,c=list(map(int,input().split()))
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})
 
def DIJKSTRA(point,d):
    cost      = {node:1e18 for node in list(d.keys())}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=list(map(int,input().split()))
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=list(map(int,input().split()))
    print((y[a]+y[b]))