AtCoder Beginner Contest 070 - Transit Tree Path

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-----
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

-----Sample Output-----
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

Difficulty: MEDIUM

Starter code:

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


import sys
readline = sys.stdin.readline
N = int(readline())
E = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = map(int, readline().split())
	E[a - 1].append((b - 1, c))
	E[b - 1].append((a - 1, c))
(Q, K) = map(int, readline().split())
dist = [-1] * N
dist[K - 1] = 0
q = [K - 1]
while q:
	x = q.pop()
	d = dist[x]
	for (i, j) in E[x]:
		if dist[i] == -1:
			dist[i] = d + j
			q.append(i)
for _ in range(Q):
	(x, y) = map(int, readline().split())
	print(dist[x - 1] + dist[y - 1])


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


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


N = int(input())
neig = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	neig[a - 1].append((b - 1, c))
	neig[b - 1].append((a - 1, c))
(Q, K) = map(int, input().split())
(S, D) = ([(K - 1, K - 1)], [0] * N)
while len(S) > 0:
	(p, pp) = S.pop()
	for (c, d) in neig[p]:
		if not c == pp:
			D[c] = D[p] + d
			S.append((c, p))
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(D[x - 1] + D[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)
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] += ((b, c),)
	G[b] += ((a, c),)
(q, k) = map(int, input().split())
d = [0] * (n + 1)

def f(v, p, u):
	d[v] = u
	for (t, c) in G[v]:
		if p != t:
			f(t, v, u + c)
f(k, 0, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	print(d[x] + d[y])


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
T = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	T[a].append([b, c])
	T[b].append([a, c])
(Q, K) = map(int, input().split())
dist = [None] * (N + 1)

def dfs(now, d):
	dist[now] = d
	for (to, c) in T[now]:
		if dist[to] is not None:
			continue
		dfs(to, d + c)
dfs(K, 0)
for _ in range(Q):
	(u, v) = map(int, input().split())
	ans = dist[u] + dist[v]
	print(ans)


from networkx import *
N = int(input())
E1 = [list(map(int, input().split())) for n in range(N - 1)]
(Q, K) = map(int, input().split())
E2 = [list(map(int, input().split())) for q in range(Q)]
G = Graph()
for (a, b, c) in E1:
	G.add_edge(a - 1, b - 1, weight=c)
D = shortest_path_length(G, weight='weight', target=K - 1)
for (x, y) in E2:
	print(D[x - 1] + D[y - 1])


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(num, cost):
	visited[num] = cost
	for item in way[num]:
		if visited[item[0]] == -1:
			dfs(item[0], cost + item[1])
	return
N = int(input())
way = [[] for i in range(N)]
visited = [-1] * N
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	way[a - 1].append([b - 1, c])
	way[b - 1].append([a - 1, c])
(Q, K) = map(int, input().split())
dfs(K - 1, 0)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(visited[x - 1] + visited[y - 1])


n = int(input())
r = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	r[a].append((b, c))
	r[b].append((a, c))
ans = [-1 for i in range(n + 1)]
(Q, k) = map(int, input().split())
q = [(k, 0)]
while len(q) > 0:
	(v, l) = q.pop()
	ans[v] = l
	for (V, L) in r[v]:
		if ans[V] == -1:
			q.append((V, l + L))
for i in range(Q):
	(x, y) = map(int, input().split())
	print(ans[x] + ans[y])


import sys
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = 1 << 50
EPS = 1e-08
mod = 10 ** 9 + 7

def intread():
	return int(sysread())

def mapline(t=int):
	return list(map(t, sysread().split()))

def mapread(t=int):
	return list(map(t, read().split()))

def dfs(current, to, dists):
	(c, c_cost) = current
	dists[c] = c_cost
	for (n, n_cost) in to[c]:
		if dists[n] == -1:
			dfs((n, c_cost + n_cost), to, dists)
	return dists

def run():
	N = intread()
	to = [[] for _ in range(N + 1)]
	for i in range(N - 1):
		(a, b, c) = mapline()
		to[a].append((b, c))
		to[b].append((a, c))
	(Q, K) = mapline()
	dists = [-1] * (N + 1)
	dists = dfs((K, 0), to, dists)
	for i in range(Q):
		(x, y) = mapline()
		print(dists[x] + dists[y])

def __starting_point():
	run()
__starting_point()


n = int(input())
g = [[] for i 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))
(q, k) = map(int, input().split())
k -= 1
c = [-1] * n
c[k] = 0
stack = [k]
while stack:
	cur = stack.pop()
	for (next_, cost) in g[cur]:
		if c[next_] < 0:
			c[next_] = c[cur] + cost
			stack.append(next_)
for i in range(q):
	(x, y) = map(lambda x: int(x) - 1, input().split())
	print(c[x] + c[y])


import sys
sys.setrecursionlimit(1000000)

def dfs(l, d, k):
	for i in l[k]:
		if d[i[0]] == -1:
			d[i[0]] = d[k] + i[1]
			dfs(l, d, i[0])
n = int(input())
l = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	l[a - 1].append([b - 1, c])
	l[b - 1].append([a - 1, c])
(q, k) = map(int, input().split())
d = [-1 for i in range(n)]
d[k - 1] = 0
dfs(l, d, k - 1)
L = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
	print(d[L[i][0] - 1] + d[L[i][1] - 1])


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
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())
dist = [-1] * N
dist[K - 1] = 0

def dfs(start, nown):
	to = T[start]
	for t in to:
		(next_node, c) = t
		if dist[next_node] != -1:
			continue
		nextn = nown + c
		dist[next_node] = nextn
		dfs(next_node, nextn)
dfs(K - 1, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)
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))
d = [0] * N

def dfs(u, p, k):
	d[u] = k
	for (w, c) in G[u]:
		if w == p:
			continue
		dfs(w, u, k + c)
(Q, K) = map(int, input().split())
dfs(K - 1, -1, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	print(d[x] + d[y])


N = int(input())
from collections import defaultdict
branch = defaultdict(dict)
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	branch[a - 1][b - 1] = c
	branch[b - 1][a - 1] = c
(Q, K) = map(int, input().split())
dist = [float('inf') for i in range(N)]
K -= 1
dist[K] = 0
check = {K}
while len(check) > 0:
	now = check.pop()
	for (nex, cost) in branch[now].items():
		if dist[nex] > dist[now] + cost:
			dist[nex] = dist[now] + cost
			check |= {nex}
for i in range(Q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


import sys
from collections import deque
N = int(sys.stdin.readline())
edges = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = map(int, sys.stdin.readline().split())
	edges[a - 1].append((b - 1, c))
	edges[b - 1].append((a - 1, c))
(Q, K) = map(int, sys.stdin.readline().split())
dist = [-1 for _ in range(N)]
visited = set()
q = deque([(K - 1, 0)])
while q:
	(p, c) = q.popleft()
	if p in visited:
		continue
	dist[p] = c
	visited.add(p)
	for (next_p, next_c) in edges[p]:
		q.append((next_p, c + next_c))
for _ in range(Q):
	(x, y) = map(int, sys.stdin.readline().split())
	print(dist[x - 1] + dist[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
d = [-1 for i in range(n)]
e = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	e[a - 1].append([b - 1, c])
	e[b - 1].append([a - 1, c])
(q, k) = map(int, input().split())

def dfs(cur, par, di):
	d[cur] = di
	for i in e[cur]:
		if d[i[0]] == -1:
			if i == par:
				continue
			dfs(i[0], cur, di + i[1])
dfs(k - 1, -1, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	print(d[x - 1] + d[y - 1])


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(now_node, parent_node, dist):
	depth[now_node] = dist
	for (next_node, w) in graph[now_node]:
		if next_node == parent_node:
			continue
		dfs(next_node, now_node, dist + w)
n = int(input())
graph = [[] for _ in range(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())
depth = [-1] * (n + 1)
dfs(k, 0, 0)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(depth[x] + depth[y])


import heapq
N = int(input())
node = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	node[a - 1].append([c, b - 1])
	node[b - 1].append([c, a - 1])
(Q, K) = map(int, input().split())
flag = [True] * N
ques = [[0, K - 1]]
D = [0] * N
while ques:
	(d1, l1) = heapq.heappop(ques)
	if flag[l1]:
		flag[l1] = False
		D[l1] = d1
		for (d2, l2) in node[l1]:
			if flag[l2]:
				heapq.heappush(ques, [d1 + d2, l2])
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(D[x - 1] + D[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)
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([y - 1, z])
	edge[y - 1].append([x - 1, z])
(q, k) = map(int, input().split())
dist = [-1] * n

def dfs(node, d):
	dist[node] = d
	for i in edge[node]:
		if dist[i[0]] == -1:
			dfs(i[0], d + i[1])
dfs(k - 1, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


N = int(input())
g = {i: [] for i in range(1, N + 1)}
l = [0] * (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())
stack = [K]
while len(stack):
	v = stack.pop()
	for (c, ln) in g[v]:
		if l[c] != 0:
			continue
		l[c] = l[v] + ln
		stack.append(c)
for q in range(Q):
	(x, y) = map(int, input().split())
	print(l[x] + l[y])


import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 12
m = 10 ** 9 + 7
N = int(input())
adj = [[] for _ in range(N)]
rtree = [None] * N

def dfs(v, parent, dist):
	rtree[v] = dist
	for (u, c) in adj[v]:
		if u == parent:
			continue
		dfs(u, v, dist + c)

def main():
	for _ in range(N - 1):
		(a, b, c) = list(map(int, input().split()))
		adj[a - 1].append((b - 1, c))
		adj[b - 1].append((a - 1, c))
	(Q, K) = list(map(int, input().split()))
	dfs(K - 1, -1, 0)
	for _ in range(Q):
		(x, y) = [int(x) - 1 for x in input().split()]
		print(rtree[x] + rtree[y])

def __starting_point():
	main()
__starting_point()


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


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())
k = k - 1
stack = [k]
dis = [-1] * n
dis[k] = 0
while len(stack) > 0:
	now = stack.pop()
	d = dis[now]
	for i in G[now]:
		if dis[i[0]] == -1:
			dis[i[0]] = d + i[1]
			stack.append(i[0])
for i in range(q):
	(x, y) = map(int, input().split())
	x = x - 1
	y = y - 1
	print(dis[x] + dis[y])


from collections import deque
INF = float('inf')
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v, w) = map(int, input().split())
	g[u - 1].append((v - 1, w))
	g[v - 1].append((u - 1, w))
(q, k) = map(int, input().split())
ds = [INF] * n
que = deque([(k - 1, 0)])
while len(que):
	(u, d) = que.popleft()
	if ds[u] != INF:
		continue
	ds[u] = d
	for (v, w) in g[u]:
		que.append((v, d + w))
for _ in range(q):
	(u, v) = map(int, input().split())
	print(ds[u - 1] + ds[v - 1])


from collections import deque
N = int(input())
G = [{} for _ in range(N + 1)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	G[a][b] = G[b][a] = c

def bfs(s):
	seen = [0 for i in range(N + 1)]
	d = [0 for i in range(N + 1)]
	cross = []
	todo = deque()
	seen[s] = 1
	todo.append(s)
	while 1:
		if len(todo) == 0:
			break
		a = todo.popleft()
		for b in G[a].keys():
			if seen[b] == 0:
				seen[b] = 1
				todo.append(b)
				d[b] += d[a] + G[a][b]
	return d
(Q, K) = map(int, input().split())
d = bfs(K)
for q in range(Q):
	(x, y) = map(int, input().split())
	print(d[x] + d[y])


from collections import deque
n = int(input())
X = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	X[a - 1].append([b - 1, c])
	X[b - 1].append([a - 1, c])
distance = [-1] * n
(q, k) = map(int, input().split())
Que = deque([[k - 1, 0]])
while Que:
	(b, c) = Que.popleft()
	distance[b] = c
	for (pb, pc) in X[b]:
		if distance[pb] == -1:
			Que.append([pb, c + pc])
for i in range(q):
	(x, y) = map(int, input().split())
	print(distance[x - 1] + distance[y - 1])


N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = list(map(int, input().split()))
	graph[a - 1].append((b - 1, c))
	graph[b - 1].append((a - 1, c))
(Q, K) = list(map(int, input().split()))
K -= 1
query = [tuple((int(x) for x in input().split())) for _ in range(Q)]
seen = {K}
v = [K]
distfromK = [0] * N
while len(v) != 0:
	for nv in graph[v[0]]:
		if nv[0] in seen:
			continue
		distfromK[nv[0]] = distfromK[v[0]] + nv[1]
		v.append(nv[0])
		seen.add(nv[0])
	v.pop(0)
for q in query:
	print(distfromK[q[0] - 1] + distfromK[q[1] - 1])


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


from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
g = [[] for i in range(n)]
for i 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()))
dist = [-1] * n

def dfs(st, depth=0):
	dist[st] = depth
	for (to, c) in g[st]:
		if dist[to] >= 0:
			continue
		dfs(to, depth + c)
dfs(k - 1, 0)
for i in range(q):
	(x, y) = list(map(int, input().split()))
	x -= 1
	y -= 1
	print(dist[x] + dist[y])


import heapq as hq
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))
(Q, K) = map(int, input().split())
INF = float('inf')
d = [INF] * N
K -= 1
d[K] = 0
q = [(0, K)]
while q:
	(dist, i) = hq.heappop(q)
	if d[i] < dist:
		continue
	for (j, w) in edges[i]:
		if d[j] > d[i] + w:
			d[j] = d[i] + w
			hq.heappush(q, (d[j], j))
for _ in range(Q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(d[x] + d[y])


import sys
sys.setrecursionlimit(1000000)
N = int(input())
X = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	X[a - 1].append((b - 1, c))
	X[b - 1].append((a - 1, c))
cost = [-1] * N

def calc(i, c):
	cost[i] = c
	for (ni, nc) in X[i]:
		if cost[ni] == -1:
			calc(ni, c + nc)
(Q, K) = map(int, input().split())
calc(K - 1, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(cost[x - 1] + cost[y - 1])


import sys
sys.setrecursionlimit(100005)
N = int(input())
edges = {n: [] for n in range(N + 1)}
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	edges[a].append((b, c))
	edges[b].append((a, c))
(Q, K) = map(int, input().split())
xy = []
for _ in range(Q):
	xy.append(tuple(map(int, input().split())))
d = [-1] * (N + 1)
d[K] = 0

def dfs(n: int):
	for (m, c) in edges[n]:
		if d[m] == -1:
			d[m] = d[n] + c
			dfs(m)
dfs(K)
for (x, y) in xy:
	print(d[x] + d[y])


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
l = [[] for i in range(n)]
C = [0] * n
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	l[a].append([b, c])
	l[b].append([a, c])

def dfs(now, par, cost):
	C[now] = cost
	L = l[now]
	for i in range(len(L)):
		if L[i][0] == par:
			continue
		dfs(L[i][0], now, cost + L[i][1])
(Q, K) = map(int, input().split())
K -= 1
dfs(K, K, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(C[x] + C[y])


import sys
sys.setrecursionlimit(10 ** 7)

def dfs(st, depth=0):
	dist[st] = depth
	for (to, c) in tree[st]:
		if dist[to] >= 0:
			continue
		dfs(to, depth + c)
N = int(input())
tree = [[] for _ in range(N)]
dist = [-1] * N
for _ 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())
dfs(K - 1, 0)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


F = lambda : map(int, input().split())
N = int(input())
abc = [[*F()] for _ in range(N - 1)]
(Q, K) = F()
xy = [[*F()] for _ in range(Q)]
G = [[] for _ in range(N + 1)]
for (a, b, c) in abc:
	G[a].append([a, b, c])
	G[b].append([b, a, c])
D = [10 ** 9 * (N + 1)] * (N + 1)
D[0] = 0
D[K] = 0
from collections import *
que = deque(G[K])
while que:
	(a, b, c) = que.popleft()
	if D[a] + c < D[b]:
		D[b] = D[a] + c
		for g in G[b]:
			que.append(g)
for (x, y) in xy:
	print(D[x] + D[y])


N = int(input())
edges = [list(map(int, input().split())) for i in range(N - 1)]
(Q, K) = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(Q)]
root = [[] for _ in range(N)]
for (a, b, c) in edges:
	root[a - 1].append((b - 1, c))
	root[b - 1].append((a - 1, c))
d = [-1] * N
s = [K - 1]
d[K - 1] = 0
while s:
	l = s.pop()
	for (i, c) in root[l]:
		if d[i] == -1:
			d[i] = d[l] + c
			s.append(i)
for i in range(Q):
	print(d[xy[i][0] - 1] + d[xy[i][1] - 1])


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 for _ in range(N)]
dist[K] = 0
q = [K]
while len(q) > 0:
	v = q.pop()
	for p in G[v]:
		nv = p[0]
		if dist[nv] != -1:
			continue
		dist[nv] = dist[v] + p[1]
		q.append(nv)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


n = int(input())
tree = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	tree[a].append([b, c])
	tree[b].append([a, c])
(q, k) = map(int, input().split())
from collections import deque
que = deque([k])
visit = [-1 for _ in range(n + 1)]
visit[k] = 0
while que:
	pos = que.popleft()
	for (i, j) in tree[pos]:
		if visit[i] < 0:
			visit[i] = visit[pos] + j
			que.append(i)
for i in range(q):
	(x, y) = map(int, input().split())
	print(visit[x] + visit[y])


n = int(input())
G = [[] for i in range(n)]
for i in range(n - 1):
	(u, v, w) = map(int, input().split())
	G[u - 1].append([v - 1, w])
	G[v - 1].append([u - 1, w])
dist = [-1] * n
from collections import deque
(Q, k) = map(int, input().split())
q = deque()
q.append(k - 1)
dist[k - 1] = 0
while q:
	cur = q.popleft()
	for (nx, nd) in G[cur]:
		if dist[nx] != -1:
			continue
		dist[nx] = dist[cur] + nd
		q.append(nx)
for i in range(Q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(dist[x] + dist[y])


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


n = int(input())
v = [[0] + [] * (n + 1) for i in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	v[a].append([b, c])
	v[b].append([a, c])
(q, k) = map(int, input().split())
l = [k]
while l:
	now = l.pop()
	for i in v[now][1:]:
		if v[i[0]][0] == 0:
			v[i[0]][0] = i[1] + v[now][0]
			l.append(i[0])
for i in range(q):
	(x, y) = map(int, input().split())
	print(v[x][0] + v[y][0])


import sys
sys.setrecursionlimit(500000)

def dfs(v, d):
	memo[v] = d
	for i in graph[v]:
		if memo[i[0]] != -1:
			continue
		dfs(i[0], d + i[1])
n = int(input())
graph = [[] for _ in range(n)]
memo = [-1] * n
for i in range(n - 1):
	(x, y, z) = map(int, input().split())
	graph[x - 1].append([y - 1, z])
	graph[y - 1].append([x - 1, z])
(q, k) = map(int, input().split())
ary = [list(map(int, input().split())) for _ in range(q)]
dfs(k - 1, 0)
for (x, y) in ary:
	print(memo[x - 1] + memo[y - 1])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
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())
D = [None] * (n + 1)

def dfs(x, d):
	D[x] = d
	for (yy, dd) in G[x]:
		if D[yy] is not None:
			continue
		dfs(yy, dd + d)
dfs(k, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	print(D[x] + D[y])


N = int(input())
edge = [list(map(int, input().split())) for i in range(N - 1)]
inf = 10 ** 15
c = [[] for i in range(N)]
for (i, j, w) in edge:
	c[i - 1].append((j - 1, w))
	c[j - 1].append((i - 1, w))
(Q, K) = map(int, input().split())
d = [inf] * N
d[K - 1] = 0
v = [0] * N
import sys
sys.setrecursionlimit(10 ** 5 + 9)

def dfs(p, v, d):
	for (n, w) in c[p]:
		if v[n] == 0:
			d[n] = min(d[n], d[p] + w)
			v[n] = 1
			dfs(n, v, d)
dfs(K - 1, v, d)
xy = [list(map(int, input().split())) for i in range(Q)]
for (x, y) in xy:
	print(d[x - 1] + d[y - 1])


n = int(input())
edges = [[] for _ in range(n + 1)]
for (a, b, c) in (map(int, input().split()) for _ in range(n - 1)):
	edges[a].append((c, b))
	edges[b].append((c, a))
(q, k) = 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 (map(int, input().split()) for _ in range(q))))))


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) = tuple(map(int, input().split()))
INF = 10 ** 9 * n + 1
dists = [INF] * n
dists[k - 1] = 0
from collections import deque
q = deque([k - 1])
while q:
	node = q.popleft()
	for (to, c) in G[node]:
		if dists[to] > dists[node] + c:
			dists[to] = dists[node] + c
			q.append(to)
for _ in range(Q):
	(s, g) = tuple(map(int, input().split()))
	print(dists[s - 1] + dists[g - 1])


from collections import deque
N = int(input())
t = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = list(map(int, input().split()))
	t[a - 1].append([b, c])
	t[b - 1].append([a, c])
(Q, K) = list(map(int, input().split()))
visited = [-1 for _ in range(N)]
visited[K - 1] = 0
que = deque()
que.append(K)
while len(que):
	now = que.popleft()
	for (nxt, c) in t[now - 1]:
		if visited[nxt - 1] != -1:
			continue
		visited[nxt - 1] = visited[now - 1] + c
		que.append(nxt)
for i in range(Q):
	(x, y) = list(map(int, input().split()))
	print(visited[x - 1] + visited[y - 1])


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
G = [[] for _ in range(N)]
length = {}
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
	length[a - 1, b - 1] = c
	length[b - 1, a - 1] = c
r = 0
dist = [0] * N
prv = [None] * N
depth = [0] * N

def dfs(v):
	for u in G[v]:
		if dist[u] > 0 or u == r:
			continue
		dist[u] = dist[v] + length[v, u]
		depth[u] = depth[v] + 1
		prv[u] = v
		dfs(u)
dfs(r)
LV = (N - 1).bit_length()

def construct(prv):
	kprv = [prv]
	S = prv
	for k in range(LV):
		T = [0] * N
		for i in range(N):
			if S[i] is None:
				continue
			T[i] = S[S[i]]
		kprv.append(T)
		S = T
	return kprv

def lca(u, v, kprv, depth):
	dd = depth[v] - depth[u]
	if dd < 0:
		(u, v) = (v, u)
		dd = -dd
	for k in range(LV + 1):
		if dd & 1:
			v = kprv[k][v]
		dd >>= 1
	if u == v:
		return u
	for k in range(LV - 1, -1, -1):
		pu = kprv[k][u]
		pv = kprv[k][v]
		if pu != pv:
			u = pu
			v = pv
	return kprv[0][u]
kprv = construct(prv)
(Q, K) = map(int, input().split())
K -= 1
ans = []
for _ in range(Q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	xr = lca(x, K, kprv, depth)
	yr = lca(y, K, kprv, depth)
	a = dist[x] + dist[K] - dist[xr] * 2 + dist[y] + dist[K] - dist[yr] * 2
	ans.append(a)
print('\n'.join(map(str, ans)))


N = int(input())
E = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	E[a].append((b, c))
	E[b].append((a, c))
(Q, K) = map(int, input().split())
qs = [tuple(map(int, input().split())) for _ in range(Q)]
stack = [(K, 0)]
dist = [0] * (N + 1)
dist[K] = 0
while stack:
	(n, c) = stack.pop()
	for (to, cost) in E[n]:
		if dist[to]:
			continue
		dist[to] = c + cost
		stack.append((to, c + cost))
for (x, y) in qs:
	print(dist[x] + dist[y])


N = int(input())
tree = {}
for _ in range(N - 1):
	(A, B, C) = [int(i) for i in input().split()]
	if A not in tree:
		tree[A] = []
	if B not in tree:
		tree[B] = []
	tree[A].append((B, C))
	tree[B].append((A, C))
c = {}
q = []
visited = set()

def dfs(a, acc):
	q.append((a, acc))
	while q:
		(n, r) = q.pop()
		c[n] = r
		visited.add(n)
		for (b, cost) in ((b, cost) for (b, cost) in tree[n] if b not in visited):
			q.append((b, cost + r))
(Q, K) = [int(i) for i in input().split()]
dfs(K, 0)
for _ in range(Q):
	(x, y) = [int(i) for i in input().split()]
	print(c[x] + c[y])


import sys
input = sys.stdin.readline
n = int(input())
G = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = [int(v) - 1 for v in input().split()]
	c += 1
	G[a].append((b, c))
	G[b].append((a, c))
(q, k) = [int(v) for v in input().split()]
k = k - 1
stack = [k]
dis = [-1] * n
dis[k] = 0
while stack != []:
	now = stack.pop()
	d = dis[now]
	for i in G[now]:
		if dis[i[0]] == -1:
			dis[i[0]] = d + i[1]
			stack.append(i[0])
for i in range(q):
	(x, y) = [int(v) - 1 for v in input().split()]
	print(dis[x] + dis[y])


import sys
N = int(input())
E = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	E[a - 1].append((b - 1, c))
	E[b - 1].append((a - 1, c))
(Q, K) = map(int, input().split())
dist = [0] * N
sys.setrecursionlimit(2 * N)

def rec(v, pred, d):
	dist[v] = d
	for (u, c) in E[v]:
		if u == pred:
			continue
		rec(u, v, d + c)
rec(K - 1, -1, 0)
ans = [0] * Q
for i in range(Q):
	(x, y) = map(int, input().split())
	ans[i] = dist[x - 1] + dist[y - 1]
[print(a) for a in ans]


from collections import deque
N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	links[a].append((b, c))
	links[b].append((a, c))
(Q, K) = map(int, input().split())
d = [float('inf')] * (N + 1)
d[K] = 0
q = deque([K])
while q:
	i = q.popleft()
	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) = map(int, input().split())
	result.append(d[x] + d[y])
print(*result, sep='\n')


from collections import deque

def inpl():
	return map(int, input().split())
N = int(input())
G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = inpl()
	G[a].append((b, c))
	G[b].append((a, c))
D = [0] * (N + 1)
(Q, K) = inpl()
DQ = deque([[K, 0]])
visited = [False] * (N + 1)
while DQ:
	(p, c) = DQ.popleft()
	D[p] = c
	visited[p] = True
	for (q, d) in G[p]:
		if not visited[q]:
			DQ.append([q, c + d])
for _ in range(Q):
	(x, y) = inpl()
	print(D[x] + D[y])


n = int(input())
ki = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	ki[a - 1].append([b - 1, c])
	ki[b - 1].append([a - 1, c])
(q, k) = map(int, input().split())
s = [0] * n
from collections import deque
d = deque()
d.append(k - 1)
while d:
	g = d.popleft()
	for i in ki[g]:
		if s[i[0]]:
			continue
		d.append(i[0])
		s[i[0]] = s[g] + i[1]
for i in range(q):
	(x, y) = map(int, input().split())
	print(s[x - 1] + s[y - 1])


import sys
from collections import deque, defaultdict, namedtuple
import heapq
from math import sqrt, factorial, gcd, ceil, atan, pi

def input():
	return sys.stdin.readline()[:-1]
import string
import operator
import random
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1000000000.0) + 7
INF = float('inf')
sys.setrecursionlimit(int(1000000.0))

def solve():
	n = int(input())
	g = defaultdict(list)
	for _ in range(n - 1):
		(a, b, c) = [int(x) for x in input().split()]
		g[a].append((b, c))
		g[b].append((a, c))
	(q, k) = [int(x) for x in input().split()]
	d = defaultdict(int)

	def dfs(v, f, dis):
		d[v] = dis
		for (to, xd) in g[v]:
			if to == f:
				continue
			dfs(to, v, dis + xd)
	dfs(k, -1, 0)
	for _ in range(q):
		(a, b) = [int(x) for x in input().split()]
		print(d[a] + d[b])
T = 1
for case in range(1, T + 1):
	ans = solve()


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
tree = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	tree[a].append((b, c))
	tree[b].append((a, c))
(q, k) = map(int, input().split())
distance = [-1 for i in range(n + 1)]

def dfs(now, pre, c):
	distance[now] = c
	for (nxt, val) in tree[now]:
		if nxt == pre:
			continue
		dfs(nxt, now, c + val)
dfs(k, -1, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	print(distance[x] + distance[y])


import sys
from heapq import heappush, heappop
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	N = int(readline())
	G = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b, c) = map(int, readline().split())
		G[a - 1].append((b - 1, c))
		G[b - 1].append((a - 1, c))
	(Q, K, *XY) = map(int, read().split())
	K -= 1
	hq = [(0, K)]
	dist = [INF] * N
	dist[K] = 0
	while hq:
		(d, v) = heappop(hq)
		if dist[v] < d:
			continue
		for (nv, cost) in G[v]:
			if dist[nv] > d + cost:
				dist[nv] = d + cost
				heappush(hq, (dist[nv], nv))
	ans = [0] * Q
	for (i, (x, y)) in enumerate(zip(*[iter(XY)] * 2)):
		ans[i] = dist[x - 1] + dist[y - 1]
	print(*ans, sep='\n')
	return

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(prev, now, fromK, t, d):
	d[now] = fromK
	for nl in t[now]:
		if nl[0] != prev:
			dfs(now, nl[0], fromK + nl[1], t, d)
N = int(input())
T = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, l) = map(int, input().split())
	T[a].append([b, l])
	T[b].append([a, l])
(Q, K) = map(int, input().split())
D = [0] * (N + 1)
dfs(-1, K, 0, T, D)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(D[x] + D[y])


from collections import defaultdict
N = int(input())
E = defaultdict(list)
W = dict()
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	E[a].append(b)
	E[b].append(a)
	W[a, b] = c
	W[b, a] = c
(Q, K) = 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) = map(int, input().split())
	print(costs[x] + costs[y])


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())
	g[a - 1].append([b - 1, c])
	g[b - 1].append([a - 1, c])
(q, k) = map(int, input().split())
qu = deque([[k - 1, 0]])
v = [0] * n
d = [0] * n
while len(qu) > 0:
	s = qu.popleft()
	v[s[0]] = 1
	for j in g[s[0]]:
		if not v[j[0]]:
			v[j[0]] = 1
			d[j[0]] = s[1] + j[1]
			qu += [[j[0], d[j[0]]]]
for i in range(q):
	(x, y) = map(int, input().split())
	print(d[x - 1] + d[y - 1])


import sys
readline = sys.stdin.readline
N = int(readline())
G = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = list(map(int, readline().split()))
	G[a - 1].append((b - 1, c))
	G[b - 1].append((a - 1, c))
(Q, K) = list(map(int, readline().split()))
dist = [0] * N
stack = [(K - 1, -1, 0)]
while stack:
	(v, parent, cost) = stack.pop()
	dist[v] = cost
	for (child, c) in G[v]:
		if child == parent:
			continue
		stack.append((child, v, cost + c))
for i in range(Q):
	(x, y) = list(map(int, readline().split()))
	print(dist[x - 1] + dist[y - 1])


N = int(input())
G = [[] * N 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))
(Q, K) = map(int, input().split())
D = [-1] * N
s = [(K - 1, 0)]
while s:
	(v, c) = s.pop()
	D[v] = c
	for (vv, cc) in G[v]:
		if D[vv] < 0:
			s.append((vv, cc + c))
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(D[x - 1] + D[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
G = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = map(lambda x: int(x) - 1, input().split())
	G[a].append([b, c + 1])
	G[b].append([a, c + 1])
(Q, K) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(Q)]
depth = [0 for i in range(N)]
depth[K - 1] = 0

def dfs(cur, p, d):
	for (i, j) in G[cur]:
		if i != p:
			depth[i] = d + j
			dfs(i, cur, d + j)
dfs(K - 1, -1, 0)
for (i, j) in A:
	print(depth[i - 1] + depth[j - 1])


from collections import 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)]
G = [[] * N for _ in range(N)]
for (a, b, c) in ABC:
	G[a - 1].append((b - 1, c))
	G[b - 1].append((a - 1, c))
D = [-1] * N
D[K - 1] = 0
q = deque()
q.append(K - 1)
while q:
	n = q.popleft()
	for (i, c) in G[n]:
		if D[i] < 0:
			q.append(i)
			D[i] = D[n] + c
for (x, y) in XY:
	print(D[x - 1] + D[y - 1])


import sys

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.append(i)
	return dist
a = []
edge = []
for l in sys.stdin:
	a.append(l.split())
V = int(a[0][0])
for i in range(V - 1):
	buf = [int(a[i + 1][0]) - 1, int(a[i + 1][1]) - 1, int(a[i + 1][2])]
	edge.append(buf)
n = int(a[V][0])
s = int(a[V][1]) - 1
ques = []
for i in range(n):
	buf = [int(a[V + i + 1][0]) - 1, int(a[V + i + 1][1]) - 1]
	ques.append(buf)
dist = BFS(s, edge, V)
for (a, b) in ques:
	res = dist[a] + dist[b]
	print(res)


def abc070_d():
	import sys
	sys.setrecursionlimit(10010010)
	read = sys.stdin.buffer.read
	inp = iter(map(int, read().split()))
	n = next(inp)
	adjlist = [[] for _ in range(n)]
	for _ in range(n - 1):
		a = next(inp) - 1
		b = next(inp) - 1
		c = next(inp)
		adjlist[a].append((b, c))
		adjlist[b].append((a, c))
	q = next(inp)
	k = next(inp) - 1
	dist = [-1] * n

	def dfs(x: int, d: int):
		dist[x] = d
		for (nx, nd) in adjlist[x]:
			if dist[nx] != -1:
				continue
			dfs(nx, d + nd)
	dfs(k, 0)
	for _ in range(q):
		x = next(inp) - 1
		y = next(inp) - 1
		ans = dist[x] + dist[y]
		print(ans)

def __starting_point():
	abc070_d()
__starting_point()


import collections
n = int(input())
arr = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(u, v, w) = map(int, input().split())
	arr[u].append([v, w])
	arr[v].append([u, w])
(m, p) = map(int, input().split())
q = collections.deque([p])
check = [False for _ in range(n + 1)]
check[p] = True
d = [0 for _ in range(n + 1)]
while 1:
	if len(q) == 0:
		break
	tmp = q.popleft()
	for (i, j) in arr[tmp]:
		if check[i] == False:
			check[i] = True
			d[i] = d[tmp] + j
			q.append(i)
for i in range(m):
	(u, v) = map(int, input().split())
	print(d[u] + d[v])


n = int(input())
abc = [list(map(int, input().split())) for _ in [0] * (n - 1)]
(q, k) = map(int, input().split())
xy = [list(map(int, input().split())) for _ in [0] * q]
g = [[] for _ in [0] * n]
[g[b - 1].append([a - 1, c]) for (a, b, c) in abc]
[g[a - 1].append([b - 1, c]) for (a, b, c) in abc]
inf = 10 ** 15
dist = [None for _ in [0] * n]
dist[k - 1] = 0
q = [k - 1]
while q:
	i = q.pop()
	gg = g[i]
	for (j, k) in gg:
		if dist[j] == None:
			dist[j] = dist[i] + k
			q.append(j)
for (x, y) in xy:
	print(dist[x - 1] + dist[y - 1])


import sys
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(MAP())

def NIJIGEN(H):
	return [list(input()) for i in range(H)]

def bfs(place, dis):
	for i in tree[place]:
		(a, b) = i
		if a not in finish:
			finish.add(a)
			disli[a] = dis + b
			bfs(a, dis + b)
N = INT()
tree = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b, c) = MAP()
	tree[a - 1].append([b - 1, c])
	tree[b - 1].append([a - 1, c])
(Q, K) = MAP()
disli = [0 for i in range(N)]
finish = set([K - 1])
bfs(K - 1, 0)
for i in range(Q):
	(a, b) = MAP()
	print(disli[a - 1] + disli[b - 1])


from collections import defaultdict as dd
from collections import deque as dq
N = int(input())
e = dd(list)
inf = 10 ** 15
for _ in range(N - 1):
	(u, v, d) = map(int, input().split())
	e[u].append((v, d))
	e[v].append((u, d))
(Q, K) = map(int, input().split())
d = [inf] * (N + 1)
d[K] = 0
q = dq([])
q.append(K)
while len(q):
	p = q.popleft()
	for t in e[p]:
		temp = d[p] + t[1]
		if d[t[0]] > temp:
			d[t[0]] = temp
			q.append(t[0])
for _ in range(Q):
	(u, v) = map(int, input().split())
	print(d[u] + d[v])


I = lambda : map(int, input().split())
(n,) = I()
G = [[] for i in [0] * -~n]
for i in G[2:]:
	(a, b, c) = I()
	G[a] += ((b, c),)
	G[b] += ((a, c),)
(q, k) = I()
s = [(k, 0, 0)]
while s:
	(v, p, u) = s.pop()
	s += [(t, v, u + c) for (t, c) in G[v] if p - t]
	G[v] = u
for p in [0] * q:
	(x, y) = I()
	print(G[x] + G[y])


import sys
sys.setrecursionlimit(1000000)
N = int(input())
dp = [0] * N
E = []
for i in range(N):
	E.append([])

def dfs(cur, pre):
	for (r, d) in E[cur]:
		if r != pre:
			dp[r] = dp[cur] + d
			dfs(r, cur)
for i in range(N - 1):
	(x, y, d) = list(map(int, input().split()))
	E[x - 1].append((y - 1, d))
	E[y - 1].append((x - 1, d))
(Q, K) = list(map(int, input().split()))
dfs(K - 1, -1)
for j in range(Q):
	(s, g) = list(map(int, input().split()))
	print(dp[s - 1] + dp[g - 1])


N = int(input())
G = [[] for _ in range(N)]
for i in range(N - 1):
	(x, y, d) = map(int, input().split())
	x -= 1
	y -= 1
	G[x].append((y, d))
	G[y].append((x, d))
(Q, K) = map(int, input().split())
stack = [K - 1]
unseen = [1] * N
dist = [float('inf')] * N
dist[K - 1] = 0
while stack:
	u = stack.pop()
	unseen[u] = 0
	for (v, d) in G[u]:
		if unseen[v]:
			dist[v] = min(dist[v], dist[u] + d)
			stack.append(v)
for q in range(Q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


import collections
import sys
sys.setrecursionlimit(int(10000000.0))

def dfs(n, pre, T, dist, d):
	dist[n] = d
	for i in T[n]:
		if i[0] != pre:
			dfs(i[0], n, T, dist, d + i[1])
N = int(input())
T = collections.defaultdict(lambda : [])
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	T[a].append((b, c))
	T[b].append((a, c))
(Q, K) = map(int, input().split())
d = {}
dfs(K, -1, T, d, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(d[x] + d[y])


n = int(input())
abc = [list(map(int, input().split())) for i in range(n - 1)]
(q, k) = map(int, input().split())
tree = [list() for i in range(n + 1)]
visited = [0] * (n + 1)
dist = [0] * (n + 1)
for (a, b, c) in abc:
	tree[a].append((b, c))
	tree[b].append((a, c))
stack = [k]
visited[k] = 1
while stack:
	now = stack.pop()
	for (NEXT, d) in tree[now]:
		if not visited[NEXT]:
			visited[NEXT] = 1
			dist[NEXT] = dist[now] + d
			stack.append(NEXT)
for i in range(q):
	(x, y) = map(int, input().split())
	print(dist[x] + dist[y])


import sys
sys.setrecursionlimit(1000000)
N = int(input())
tree = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	tree[a].append([b, c])
	tree[b].append([a, c])
(Q, K) = map(int, input().split())
K -= 1
dis = [0] * N

def main(v, p, d):
	dis[v] = d
	for (x, y) in tree[v]:
		if x == p:
			continue
		main(x, v, d + y)
main(K, -1, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	ans = dis[x - 1] + dis[y - 1]
	print(ans)


import sys
sys.setrecursionlimit(100000000)

def dfs(cur, par, d):
	dist[cur] = d
	for (nx, nx_dist) in G[cur]:
		if nx == par:
			continue
		dfs(nx, cur, d + nx_dist)
n = int(input())
G = [[] for i in range(n)]
dist = [0] * 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())
k -= 1
dfs(k, -1, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(dist[x] + dist[y])


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
l = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	l[a - 1].append([b - 1, c])
	l[b - 1].append([a - 1, c])
(q, k) = map(int, input().split())
dist = [-1] * n
dist[k - 1] = 0

def dfs(v):
	for (nv, c) in l[v]:
		if dist[nv] == -1:
			dist[nv] = dist[v] + c
			dfs(nv)
dfs(k - 1)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n = int(input())
li = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, dist) = map(int, input().split())
	li[a - 1].append((b - 1, dist))
	li[b - 1].append((a - 1, dist))
(q, k) = map(int, input().split())
tdp = [-1] * n
tdp[k - 1] = 0

def dfs(x):
	for node in li[x]:
		if tdp[node[0]] == -1:
			tdp[node[0]] = tdp[x] + node[1]
			dfs(node[0])
dfs(k - 1)
for i in range(q):
	(a, b) = map(int, input().split())
	print(tdp[a - 1] + tdp[b - 1])


import sys
input = sys.stdin.readline
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)]
G = [[] * N for _ in range(N)]
for (a, b, c) in ABC:
	G[a - 1].append((b - 1, c))
	G[b - 1].append((a - 1, c))
D = [-1] * N
s = [(K - 1, 0)]
while s:
	(v, c) = s.pop()
	D[v] = c
	for (vv, cc) in G[v]:
		if D[vv] < 0:
			s.append((vv, cc + c))
for (x, y) in XY:
	print(D[x - 1] + D[y - 1])


import sys

def input():
	return sys.stdin.readline().strip()
from collections import deque

def main():
	N = int(input())
	info = [tuple(map(int, input().split())) for _ in range(N - 1)]
	(Q, K) = map(int, input().split())
	queries = [tuple(map(int, input().split())) for _ in range(Q)]
	to = [[] for _ in range(N)]
	for (a, b, c) in info:
		a -= 1
		b -= 1
		to[a].append((b, c))
		to[b].append((a, c))
	INF = 10 ** 18
	dist = [INF] * N

	def dfs(s):
		stack = deque()
		push = stack.append
		pop = stack.pop
		dist[s] = 0
		push(s)
		while stack:
			now = pop()
			now_cost = dist[now]
			for (nv, c) in to[now]:
				if dist[nv] != INF:
					continue
				dist[nv] = now_cost + c
				push(nv)
	K -= 1
	dfs(K)
	ans = []
	for (x, y) in queries:
		x -= 1
		y -= 1
		xy = dist[x] + dist[y]
		ans.append(xy)
	print(*ans, sep='\n')

def __starting_point():
	main()
__starting_point()


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 for i in range(N)]
D[K] = 0
stack = [(K, g[0], g[1]) for g in G[K]]
while stack:
	(a, b, c) = stack.pop()
	if D[b] != INF:
		continue
	D[b] = D[a] + c
	stack.extend([(b, g[0], g[1]) for g in G[b]])
for i in range(Q):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	print(D[x] + D[y])


n = int(input())
l = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	l[a - 1].append([b - 1, c])
	l[b - 1].append([a - 1, c])
ans = [-1] * n
(q, k) = map(int, input().split())
ans[k - 1] = 0
from collections import deque
d = deque([k - 1])
while d:
	now = d.pop()
	for x in l[now]:
		(a, b) = x
		if ans[a] < 0:
			ans[a] = ans[now] + b
			d.append(a)
for i in range(q):
	(a, b) = map(int, input().split())
	print(ans[a - 1] + ans[b - 1])


import sys

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

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
from collections import deque
from heapq import heappop, heappush

def main():

	def dijkstra(k):

		def push(v, x):
			if dist[v] <= x:
				return
			dist[v] = x
			heappush(q, (x, v))
		inf = 10 ** 18
		dist = [inf] * n
		q = []
		push(k, 0)
		while q:
			(x, v) = heappop(q)
			if x > dist[v]:
				continue
			for (nv, c) in g[v]:
				push(nv, x + c)
		return dist
	n = ii()
	g = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b, c) = mi()
		a -= 1
		b -= 1
		g[a].append((b, c))
		g[b].append((a, c))
	(q, k) = mi()
	k -= 1
	dist = dijkstra(k)
	for i in range(q):
		(a, b) = mi()
		a -= 1
		b -= 1
		print(dist[a] + dist[b])

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
N = int(input())
g = [[] for _ 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())
cost = [-1] * (N + 1)
cost[K] = 0
temp = [K]
while temp:
	p = temp.pop()
	for q in g[p]:
		if cost[q[0]] == -1:
			cost[q[0]] = cost[p] + q[1]
			temp.append(q[0])
for i in range(Q):
	(x, y) = map(int, input().split())
	print(cost[x] + cost[y])


n = int(input())
E = [[] for i in range(n)]
for i in range(n - 1):
	(ai, bi, ci) = map(int, input().split())
	ai -= 1
	bi -= 1
	E[ai].append((bi, ci))
	E[bi].append((ai, ci))
from collections import deque
Q = deque()
(q, k) = map(int, input().split())
k -= 1
Q.append(k)
d = [-1] * n
d[k] = 0
while Q:
	v = Q.popleft()
	for (u, c) in E[v]:
		if d[u] < 0:
			d[u] = d[v] + c
			Q.append(u)
for _ in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(d[x] + d[y])


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

def dijkstra(s, N, G):
	d = [float('inf')] * N
	d[s] = 0
	hq = [[0, s]]
	heapq.heapify(hq)
	while len(hq) > 0:
		(v, i) = heapq.heappop(hq)
		if d[i] < v:
			continue
		for (c, j) in G[i]:
			if d[j] > d[i] + c:
				d[j] = d[i] + c
				heapq.heappush(hq, [d[j], j])
	return d
D = dijkstra(K - 1, N, G)
dist = [0] * Q
for i in range(Q):
	(x, y) = map(int, input().split())
	dist[i] = D[x - 1] + D[y - 1]
for d in dist:
	print(d)


from heapq import heappop, heappush
N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	links[a].append((b, c))
	links[b].append((a, c))
(Q, K) = map(int, input().split())
d = [float('inf')] * (N + 1)
d[K] = 0
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
			heappush(q, (alt, v))
result = []
for _ in range(Q):
	(x, y) = map(int, input().split())
	result.append(d[x] + d[y])
print(*result, sep='\n')


n = int(input())
g = [[] for i 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])
(q, k) = map(int, input().split())
k -= 1
con = [-1] * n
con[k] = 0
stack = [k]
while stack:
	cur = stack.pop()
	for (i, j) in g[cur]:
		if con[i] == -1:
			con[i] = con[cur] + j
			stack.append(i)
for i in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(con[x] + con[y])


import sys
sys.setrecursionlimit(1000000)
N = int(input())
n = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	n[a].append([b, c])
	n[b].append([a, c])
L = [-1 for i in range(N + 1)]
(Q, K) = map(int, input().split())
L[K] = 0

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


import copy
import random
import bisect
import fractions
import math
import sys
import collections
from decimal import Decimal
mod = 10 ** 9 + 7
sys.setrecursionlimit(mod)
d = collections.deque()

def LI():
	return list(map(int, sys.stdin.readline().split()))
N = int(input())
weights = {}
roots = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = LI()
	a -= 1
	b -= 1
	roots[a].append(b)
	roots[b].append(a)
	weights[a, b] = c
	weights[b, a] = c
(Q, K) = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
	(x, y) = LI()
	x -= 1
	y -= 1
	xy[i] = [x, y]
visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0
while len(queue) > 0:
	node = queue.popleft()
	cnt = visited[node]
	for n_node in roots[node]:
		if visited[n_node] == -1:
			visited[n_node] = cnt + weights[node, n_node]
			queue.append(n_node)
for (x, y) in xy:
	print(visited[x] + visited[y])


from heapq import heapify, heappop, heappush, heappushpop
INF = float('inf')

def dijkstra(s, n, g):
	seen = [False] * n
	cost = [INF] * n
	cost[s] = 0
	next_q = [(0, s)]
	heapify(next_q)
	while len(next_q) > 0:
		(c, i) = heappop(next_q)
		if cost[i] < c:
			continue
		for (nedge, ncost) in g[i]:
			nc = cost[i] + ncost
			if cost[nedge] > nc:
				cost[nedge] = nc
				heappush(next_q, (nc, nedge))
	return cost

def main():
	N = int(input())
	graph_F = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b, c) = map(int, input().split())
		a -= 1
		b -= 1
		graph_F[a].append((b, c))
		graph_F[b].append((a, c))
	(Q, K) = map(int, input().split())
	K -= 1
	F = dijkstra(K, N, graph_F)
	for _ in range(Q):
		(x, y) = map(int, input().split())
		print(F[x - 1] + F[y - 1])

def __starting_point():
	main()
__starting_point()


from queue import Queue
INF = float('inf')
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v, w) = map(int, input().split())
	g[u - 1].append((v - 1, w))
	g[v - 1].append((u - 1, w))
(q, k) = map(int, input().split())
ds = [INF] * n
ds[k - 1] = 0
que = Queue()
que.put((k - 1, 0))
while not que.empty():
	(u, d) = que.get()
	for (v, w) in g[u]:
		if ds[v] == INF:
			ds[v] = d + w
			que.put((v, d + w))
for _ in range(q):
	(u, v) = map(int, input().split())
	print(ds[u - 1] + ds[v - 1])


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


n = int(input())
es = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	es[a - 1].append((b - 1, c))
	es[b - 1].append((a - 1, c))
(q, k) = map(int, input().split())
k -= 1
dist = [float('inf')] * n
dist[k] = 0
stack = [k]
while stack:
	now = stack.pop()
	for (e, w) in es[now]:
		if dist[e] == float('inf'):
			dist[e] = dist[now] + w
			stack.append(e)
for _ in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(dist[x] + dist[y])


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(v: int, p: int=-1, s: int=0):
	dist[v] = s
	for (i, j) in t[v]:
		if i == p:
			continue
		dfs(i, v, s + j)
n = int(input())
t = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	t[a].append((b, c))
	t[b].append((a, c))
(q, k) = map(int, input().split())
k -= 1
dist = [0] * n
dfs(k)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


N = int(input())
f = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	f[a - 1].append([b - 1, c])
	f[b - 1].append([a - 1, c])
from collections import deque
d = deque()
s = [-1] * N
(Q, K) = map(int, input().split())
d.append(K - 1)
s[K - 1] = 0
while len(d) > 0:
	z = d.popleft()
	for (i, j) in f[z]:
		if s[i] == -1:
			s[i] = j + s[z]
			d.append(i)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(s[x - 1] + s[y - 1])


from collections import deque
n = int(input())
G = [[] for i in range(n)]
dist = [-1] * 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())
k -= 1
q = deque()
q.append(k)
dist[k] = 0
while q:
	cur = q.popleft()
	for (nx, nx_d) in G[cur]:
		if dist[nx] != -1:
			continue
		dist[nx] = dist[cur] + nx_d
		q.append(nx)
for i in range(Q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(dist[x] + dist[y])


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
graph = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b, c) = 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) = map(int, input().split())
K -= 1
d = [-1] * N
d[K] = 0
dfs(K)
for i in range(Q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(d[x] + d[y])


from math import ceil, floor, factorial, gcd, sqrt, log2, cos, sin, tan, acos, asin, atan, degrees, radians, pi, inf
from itertools import accumulate, groupby, permutations, combinations, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import Queue, LifoQueue, PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP1():
	return map(lambda x: int(x) - 1, input().split())

def LIST():
	return list(MAP())

def solve():
	N = INT()
	adj = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b, c) = MAP()
		adj[a - 1].append([b - 1, c])
		adj[b - 1].append([a - 1, c])
	(Q, K) = MAP()
	K -= 1
	d = [inf] * N
	d[K] = 0
	que = []
	heappush(que, K)
	while que:
		v = heappop(que)
		for (b, c) in adj[v]:
			if d[b] > d[v] + c:
				d[b] = d[v] + c
				heappush(que, b)
	for i in range(Q):
		(x, y) = MAP()
		print(d[x - 1] + d[y - 1])

def __starting_point():
	solve()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
G = [[] for _ 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())
query = [list(map(int, input().split())) for _ in range(Q)]

def dfs(v, pv=-1, d=0):
	dist[v] = d
	for (nv, nd) in G[v]:
		if nv == pv:
			continue
		dfs(nv, v, d + nd)
dist = [0] * N
dfs(K - 1)
for (x, y) in query:
	(x, y) = (x - 1, y - 1)
	print(dist[x] + dist[y])


import sys
sys.setrecursionlimit(1000000)
N = int(input())
T = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	T[a].append((b, c))
	T[b].append((a, c))
(Q, K) = map(int, input().split())
D = [0] * (N + 1)

def f(v, p, cost):
	global T, K, D
	for C in T[v]:
		if C[0] != p:
			D[C[0]] = cost + C[1]
			f(C[0], v, cost + C[1])
f(K, 0, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(D[x] + D[y])


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
Edges = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	Edges[a].append((b, c))
	Edges[b].append((a, c))
D = [float('inf') for i in range(N)]

def dfs(v, p, d):
	D[v] = d
	for (e1, e2) in Edges[v]:
		if e1 != p:
			dfs(e1, v, d + e2)
(Q, K) = map(int, input().split())
dfs(K - 1, -1, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(D[x - 1] + D[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
G = [[] for i in [0] * -~n]
for I in [lambda : map(int, input().split())] * ~-n:
	(a, b, c) = I()
	G[a] += ((b, c),)
	G[b] += ((a, c),)
(q, k) = I()
d = [0] * -~n

def f(v, p, u):
	d[v] = u
	for (t, c) in G[v]:
		p == t or f(t, v, u + c)
f(k, 0, 0)
for p in [print] * q:
	(x, y) = I()
	p(d[x] + d[y])


N = int(input())
G = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b, c) = list(map(int, input().split()))
	G[a - 1].append([b - 1, c])
	G[b - 1].append([a - 1, c])
(Q, K) = list(map(int, input().split()))
SD = [0] * N
seen = [0] * N
stack = []
stack.append([K - 1, 0])
seen[K - 1] = 1
while stack:
	(x, d) = stack.pop()
	for (y, d0) in G[x]:
		if seen[y] == 0:
			SD[y] = d + d0
			stack.append([y, d + d0])
			seen[y] = 1
for i in range(Q):
	(x, y) = list(map(int, input().split()))
	ans = SD[x - 1] + SD[y - 1]
	print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
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())
SD = [0] * N

def DFS(v, p, d):
	SD[v] = d
	for (i, co) in G[v]:
		if i == p:
			continue
		DFS(i, v, d + co)
	return
DFS(K - 1, -1, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	ans = SD[x - 1] + SD[y - 1]
	print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
n = int(input())
edge = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	edge[a].append((b, c))
	edge[b].append((a, c))
(q, k) = map(int, input().split())
dis = [None] * (n + 1)

def set_dist(x, d):
	dis[x] = d
	for (y, f) in edge[x]:
		if dis[y] is not None:
			continue
		set_dist(y, d + f)
set_dist(k, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	print(dis[x] + dis[y])


N = int(input())
G = [[] for n in range(N)]
for n 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())
d = N * [-1]
d[K - 1] = 0
q = [K - 1]
while q:
	t = q.pop()
	for (b, c) in G[t]:
		if d[b] == -1:
			d[b] = d[t] + c
			q.append(b)
for q in range(Q):
	(x, y) = map(int, input().split())
	print(d[x - 1] + d[y - 1])


from collections import deque
(n, *t) = map(int, open(0).read().split())
con = [[] for _ in range(n)]
dist_f_k = [0] * n
for (a, b, c) in zip(t[:3 * n - 3:3], t[1::3], t[2::3]):
	con[a - 1].append((b - 1, c))
	con[b - 1].append((a - 1, c))
k = t[3 * n - 2]
que = deque([k - 1])
while que:
	cur = que.popleft()
	for (nxt, dd) in con[cur]:
		if dist_f_k[nxt] == 0 and nxt != k - 1:
			que.append(nxt)
			dist_f_k[nxt] = dist_f_k[cur] + dd
for (x, y) in zip(t[3 * n - 1::2], t[3 * n::2]):
	print(dist_f_k[x - 1] + dist_f_k[y - 1])


n = int(input())
abc = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	abc[a].append([b, c])
	abc[b].append([a, c])
from collections import deque
(q, k) = map(int, input().split())
visited = [0] * (n + 1)
distance = [0] * (n + 1)
que = deque()
que.append(k)
visited[k] += 1
count = 0
while que:
	x = que.pop()
	for y in abc[x]:
		if visited[y[0]] == 0:
			distance[y[0]] += distance[x] + y[1]
			visited[y[0]] += 1
			que.appendleft(y[0])
for j in range(q):
	(c, d) = map(int, input().split())
	print(distance[c] + distance[d])


n = int(input())
abc = [list(map(int, input().split())) for _ in [0] * (n - 1)]
(q, k) = map(int, input().split())
xy = [list(map(int, input().split())) for _ in [0] * q]
k -= 1
tree = [[] for _ in [0] * n]
dist = [-1] * n
dist[k] = 0
[tree[a - 1].append([b - 1, c]) for (a, b, c) in abc]
[tree[b - 1].append([a - 1, c]) for (a, b, c) in abc]
q = [k]
while q:
	qq = []
	for i in q:
		for (j, k) in tree[i]:
			if dist[j] < 0:
				dist[j] = dist[i] + k
				qq.append(j)
	q = qq
for (x, y) in xy:
	print(dist[x - 1] + dist[y - 1])


import sys
from collections import defaultdict
from heapq import heappush, heappop

def input():
	return sys.stdin.readline().strip()

def dijkstra(adj_list, start):
	n = len(adj_list)
	dist = [float('inf')] * n
	dist[start] = 0
	pq = []
	heappush(pq, (0, start))
	visited = set()
	while pq:
		(w, v) = heappop(pq)
		if dist[v] < w:
			continue
		visited.add(v)
		for (nv, nw) in adj_list[v]:
			if nv in visited:
				continue
			if dist[nv] > dist[v] + nw:
				dist[nv] = dist[v] + nw
				heappush(pq, (dist[nv], nv))
	return dist
N = int(input())
g = defaultdict(list)
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
d = dijkstra(g, K)
ans = []
for _ in range(Q):
	(x, y) = list(map(int, input().split()))
	x -= 1
	y -= 1
	print(d[x] + d[y])


import sys
input = sys.stdin.readline
n = int(input())
Tree = [[] for _ in range(n)]
for _ 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())
dist = [float('inf')] * n
dist[k - 1] = 0
stack = [k - 1]
while stack != []:
	p = stack.pop()
	for q in Tree[p]:
		(qp, ql) = (q[0], q[1])
		if dist[qp] == float('inf'):
			dist[qp] = dist[p] + ql
			stack.append(qp)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


from collections import defaultdict as dd
from collections import deque
N = int(input())
D = dd(list)
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	D[a - 1].append((b - 1, c))
	D[b - 1].append((a - 1, c))
(Q, K) = map(int, input().split())
K -= 1
L = [0 for _ in range(N)]
q = deque([])
q.append(K)
while len(q) > 0:
	a = q.pop()
	for (b, c) in D[a]:
		if L[b] == 0:
			L[b] = L[a] + c
			q.append(b)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(L[x - 1] + L[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(v, p, d):
	for (i, j) in tree[v]:
		if i != p:
			depth[i] = d + j
			dfs(i, v, d + j)
N = int(input())
tree = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	tree[a].append((b, c))
	tree[b].append((a, c))
(Q, K) = map(int, input().split())
depth = [0 for i in range(N)]
depth[K - 1] = 0
dfs(K - 1, -1, 0)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(depth[x - 1] + depth[y - 1])


from collections import deque
n = int(input())
con = [[] for _ in range(n)]
dist_f_k = [0] * n
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	con[a - 1].append((b - 1, c))
	con[b - 1].append((a - 1, c))
(q, k) = map(int, input().split())
que = deque([k - 1])
while que:
	cur = que.popleft()
	for (nxt, dd) in con[cur]:
		if dist_f_k[nxt] == 0 and nxt != k - 1:
			que.append(nxt)
			dist_f_k[nxt] = dist_f_k[cur] + dd
for _ in range(q):
	(x, y) = map(int, input().split())
	print(dist_f_k[x - 1] + dist_f_k[y - 1])


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v, w) = list(map(int, input().split()))
	graph[u - 1].append((v - 1, w))
	graph[v - 1].append((u - 1, w))
(q, k) = list(map(int, input().split()))
k -= 1
dist = [-1] * n

def dfs(now, parent, d):
	dist[now] = d
	for i in graph[now]:
		if i[0] == parent:
			continue
		else:
			dfs(i[0], now, d + i[1])
dfs(k, -1, 0)
for _ in range(q):
	(x, y) = list(map(int, input().split()))
	x -= 1
	y -= 1
	print(dist[x] + dist[y])


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
from collections import defaultdict
d = defaultdict(list)
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	d[a - 1].append((b - 1, c))
	d[b - 1].append((a - 1, c))
(q, k) = map(int, input().split())
global dist
dist = [-1 for _ in range(n)]

def dfs(l, pos):
	dist[pos] = l
	for (to, c) in d[pos]:
		if dist[to] == -1:
			dfs(l + c, to)
dfs(0, k - 1)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])


import collections
n = int(input())
route = {i + 1: {} for i in range(n)}
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	route[a][b] = c
	route[b][a] = c
(q, k) = map(int, input().split())
queue = collections.deque([k])
length = [0] * (n + 1)
while queue:
	search = queue.popleft()
	pairs = []
	for (i, j) in route[search].items():
		queue.append(i)
		length[i] = length[search] + j
		pairs.append([search, i])
	for (i, j) in pairs:
		del route[i][j]
		del route[j][i]
for i in range(q):
	(x, y) = map(int, input().split())
	print(length[x] + length[y])


N = int(input())
T = {i: [] for i in range(N)}
for _ 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())
(S, D) = ([(-1, K - 1)], [0] * N)
while len(S) > 0:
	(p, c) = S.pop()
	for (g, d) in T[c]:
		if g != p:
			D[g] = D[c] + d
			S.append((c, g))
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(D[x - 1] + D[y - 1])


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


from collections import deque
n = int(input())
e = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	e[a].append([b, c])
	e[b].append([a, c])
(m, k) = map(int, input().split())
k -= 1
d = [-1] * n
d[k] = 0
q = deque()
q.append([k, 0])
while q:
	(f, cc) = q.pop()
	for (t, nc) in e[f]:
		if d[t] == -1:
			d[t] = cc + nc
			q.append([t, d[t]])
for i in range(m):
	(f, t) = map(int, input().split())
	f -= 1
	t -= 1
	print(d[f] + d[t])


import sys
sys.setrecursionlimit(20000000)
N = int(input())
ARR = [list(map(int, input().split())) for i in range(N - 1)]
(Q, K) = map(int, input().split())
BRR = [list(map(int, input().split())) for i in range(Q)]

def prepare(arr, n):
	links = [[] for i in range(n)]
	depth = [0 for i in range(n)]
	for i in range(n - 1):
		startNode = arr[i][0] - 1
		endNode = arr[i][1] - 1
		dist = arr[i][2]
		links[startNode].append((endNode, dist))
		links[endNode].append((startNode, dist))
	return (links, depth)

def dfs(currentNode, parrentNode=-1, dist=0):
	childNodes = links[currentNode]
	depths[currentNode] = dist
	for (childNode, childDistance) in childNodes:
		if childNode == parrentNode:
			continue
		dfs(childNode, currentNode, dist + childDistance)
(links, depths) = prepare(ARR, N)
dfs(K - 1)
for i in range(Q):
	p1 = BRR[i][0] - 1
	p2 = BRR[i][1] - 1
	d1 = depths[p1]
	d2 = depths[p2]
	print(d1 + d2)


N = int(input())
List = [[] for _ in range(N)]
ans = [-1] * N
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	List[a - 1].append((b - 1, c))
	List[b - 1].append((a - 1, c))
(Q, K) = 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) = map(int, input().split())
	print(ans[x - 1] + ans[y - 1])


def Graph(ab):
	G = [[] for i in range(n)]
	for (a, b, c) in ab:
		G[a - 1].append([b, c])
		G[b - 1].append([a, c])
	return G
from collections import deque

def bfs(k):
	q = deque()
	q.append((k, -1, 0))
	dis = [0] * n
	while q:
		(V, P, cnt) = q.popleft()
		for (nv, d) in G[V - 1]:
			if nv == P:
				continue
			dis[nv - 1] = cnt + d
			q.append((nv, V, cnt + d))
	return dis
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
G = Graph(abc)
(q, k) = map(int, input().split())
dis = bfs(k)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(dis[x - 1] + dis[y - 1])


from collections import deque
n = int(input())
l = [[] for _ in [0] * n]
for _ in [0] * (n - 1):
	(a, b, c) = map(int, input().split())
	l[a - 1].extend([(b - 1, c)])
	l[b - 1].extend([(a - 1, c)])
(q, k) = map(int, input().split())
dst = [0 for _ in [0] * n]
que = deque([])
(v, p, d) = (k - 1, -1, 0)
que.append((v, p, d))
while que:
	(v, p, d) = que.pop()
	dst[v] = d
	for (i, j) in l[v]:
		if i == p:
			continue
		que.append((i, v, d + j))
for _ in [0] * q:
	(x, y) = map(int, input().split())
	print(dst[x - 1] + dst[y - 1])


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


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(v, p, d):
	dist[v] = d
	for (nv, nd) in G[v]:
		if nv == p:
			continue
		dfs(nv, v, d + nd)
N = int(input())
G = [[] for i in range(N)]
dist = [-1] * 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())
dfs(K - 1, -1, 0)
for i in range(Q):
	(x, y) = map(lambda x: int(x) - 1, input().split())
	print(dist[x] + dist[y])


N = int(input())
abclist = [list(map(int, input().split())) for _ in range(N - 1)]
(Q, K) = map(int, input().split())
xylist = [list(map(int, input().split())) for _ in range(Q)]
from heapq import heapify, heappush, heappop
inf = float('inf')

def dijkstra(graph, start):
	vsize = len(graph)
	dist = [inf] * vsize
	seen = [False] * vsize
	prev = [None] * vsize
	pq = []
	heapify(pq)
	dist[start] = 0
	heappush(pq, (0, start))
	while pq:
		(cost, u) = heappop(pq)
		seen[u] = True
		if dist[u] < cost:
			continue
		for (v, w) in graph[u]:
			temp_cost = dist[u] + w
			if not seen[v] and temp_cost < dist[v]:
				dist[v] = temp_cost
				prev[v] = u
				heappush(pq, (dist[v], v))
	return (dist, prev)
graph = [[] for _ in range(N)]
for (a, b, c) in abclist:
	graph[a - 1].append((b - 1, c))
	graph[b - 1].append((a - 1, c))
(shortest_paths, prev) = dijkstra(graph, K - 1)
for (x, y) in xylist:
	print(shortest_paths[x - 1] + shortest_paths[y - 1])


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
to = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	to[a].append([b, c])
	to[b].append([a, c])
(Q, K) = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]
dist = [0] * N

def dfs(v, pv, dis):
	for i in to[v]:
		if i[0] != pv:
			dfs(i[0], v, dis + i[1])
	dist[v] = dis
dfs(K - 1, -1, 0)
for (x, y) in xy:
	print(dist[x - 1] + dist[y - 1])


import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque, Counter
from decimal import Decimal
import functools

def v():
	return input()

def k():
	return int(input())

def S():
	return input().split()

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

def X():
	return list(input())

def L():
	return list(input().split())

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

def lcm(a, b):
	return a * b // math.gcd(a, b)
sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7
cnt = 0
ans = 0
inf = float('inf')
al = 'abcdefghijklmnopqrstuvwxyz'
AL = al.upper()
N = k()
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = I()
	edge[a].append((b, c))
	edge[b].append((a, c))
(Q, K) = I()
dist = [None] * (N + 1)

def dfs(x, d):
	dist[x] = d
	for (y, dd) in edge[x]:
		if dist[y] is not None:
			continue
		dfs(y, d + dd)
dfs(K, 0)
for _ in range(Q):
	(x, y) = I()
	print(dist[x] + dist[y])


import sys
sys.setrecursionlimit(500000)
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N - 1)]
(Q, K) = map(int, input().split())
D = [0] * (N + 1)
L = [[] for i in range(N + 1)]
for (a, b, c) in ABC:
	L[a].append([b, c])
	L[b].append([a, c])

def dfs(n, np):
	for nc in L[n]:
		if nc[0] == np:
			continue
		else:
			D[nc[0]] = D[n] + nc[1]
			dfs(nc[0], n)
dfs(K, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(D[x] + D[y])


import sys
sys.setrecursionlimit(4100000)
N = int(input())
INF = 10 ** 14
edges = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	edges[a - 1].append((b - 1, c))
	edges[b - 1].append((a - 1, c))
(Q, K) = map(int, input().split())
d = [INF] * N
d[K - 1] = 0

def dfs(x):
	for (u, cost) in edges[x]:
		if d[u] == INF:
			d[u] = d[x] + cost
			dfs(u)
dfs(K - 1)
for _ in range(Q):
	(x, y) = map(int, input().split())
	ans = d[x - 1] + d[y - 1]
	print(ans)


from collections import deque
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].append([b - 1, c])
	tree[b - 1].append([a - 1, c])

def BFS(s):
	dist = [-1 for i in range(n)]
	dist[s] = 0
	que = deque()
	que.append(s)
	while que:
		x = que.popleft()
		for (i, c) in tree[x]:
			if dist[i] == -1:
				que.append(i)
				dist[i] = dist[x] + c
	return dist
(q, k) = map(int, input().split())
k_dist = BFS(k - 1)
for i in range(q):
	(x, y) = map(int, input().split())
	print(k_dist[x - 1] + k_dist[y - 1])


N = int(input())
links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	links[a].append([b, c])
	links[b].append([a, c])
(Q, K) = map(int, input().split())
length = [-1] * (N + 1)
length[K] = 0
import heapq
q = [[tmp[1], tmp[0], K] for tmp in links[K]]
heapq.heapify(q)
while q:
	tmp = heapq.heappop(q)
	length[tmp[1]] = tmp[0] + 0
	for x in links[tmp[1]]:
		if tmp[2] != x[0]:
			heapq.heappush(q, [tmp[0] + x[1], x[0], tmp[1]])
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(length[x] + length[y])


n = int(input())
abc = [list(map(int, input().split())) for i in range(n - 1)]
(q, k) = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(q)]
lst = [0] * (n + 1)
data = [[] for i in range(n + 1)]
flag = [0] * (n + 1)
for u in abc:
	(a, b, c) = u
	data[a].append([b, c])
	data[b].append([a, c])
que = [k]
flag[k] = 1
while que:
	h = que.pop()
	for u in data[h]:
		(d, c) = u
		if flag[d] == 0:
			lst[d] = lst[h] + c
			que.append(d)
			flag[d] = 1
for u in xy:
	(x, y) = u
	print(lst[x] + lst[y])


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	T[a].append([b, c])
	T[b].append([a, c])
(Q, K) = map(int, input().split())
K -= 1
dist = [-1] * N
dist[K] = 0

def dfs(n):
	for (to, cost) in T[n]:
		if dist[to] < 0:
			dist[to] = dist[n] + cost
			dfs(to)
dfs(K)
for q in range(Q):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	print(dist[x] + dist[y])


from collections import deque
N = int(input())
A = [list(map(int, input().split())) for _ in range(N - 1)]
(Q, K) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]
d = [[] for _ in range(N)]
for (a, b, c) in A:
	d[a - 1].append([b - 1, c])
	d[b - 1].append([a - 1, c])
c = [0] * N
f = [False] * N
f[K - 1] = True
q = deque([K - 1])
while q:
	now = q.popleft()
	for (nex, cost) in d[now]:
		if f[nex]:
			continue
		c[nex] = c[now] + cost
		f[nex] = True
		q.append(nex)
for (x, y) in X:
	print(c[x - 1] + c[y - 1])


import queue
n = int(input())
INF = 10 ** 18
e = [[] for _ in range(n + 1)]
d = [INF] * (n + 1)
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	e[a].append((b, c))
	e[b].append((a, c))
(q, k) = map(int, input().split())
que = queue.Queue()
que.put(k)
d[k] = 0
while not que.empty():
	x = que.get()
	for (i, c) in e[x]:
		if d[i] == INF:
			que.put(i)
			d[i] = d[x] + c
for _ in range(q):
	(x, y) = map(int, input().split())
	print(d[x] + d[y])


from collections import defaultdict, deque
n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
(q, k) = map(int, input().split())
xy = [tuple(map(int, input().split())) for _ in range(q)]
stack = [-1] * (n + 1)
stack[k] = 0
ed = defaultdict(list)
wt = defaultdict(int)
for e in edges:
	ed[e[0]].append(e[1])
	ed[e[1]].append(e[0])
	wt[e[0], e[1]] = e[2]
	wt[e[1], e[0]] = e[2]
ce = deque([(k, x) for x in ed[k]])
ne = deque()
while True:
	while ce:
		e = ce.pop()
		stack[e[1]] = stack[e[0]] + wt[e]
		for v in ed[e[1]]:
			if stack[v] < 0:
				ne.append((e[1], v))
	if not ne:
		break
	ce.extend(ne)
	ne.clear()
for que in xy:
	print(stack[que[0]] + stack[que[1]])


from collections import deque
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N - 1)]
(q, K) = map(int, input().split())
graph = [[] for i in range(N + 1)]
for (i, j, k) in abc:
	graph[i].append((j, k))
	graph[j].append((i, k))
r = [-1 for i in range(N + 1)]
Q = deque()
Q.append(K)
r[K] = 0
while Q:
	x = Q.popleft()
	for (to, dis) in graph[x]:
		if r[to] == -1:
			r[to] = r[x] + dis
			Q.append(to)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(r[x] + r[y])


N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
	[a, b, c] = [int(x) for x in input().split()]
	T[a - 1].append((b - 1, c))
	T[b - 1].append((a - 1, c))
[Q, K] = [int(x) for x in input().split()]
L = [[0, 0] for i in range(N)]
L[K - 1] = [0, 1]
q = [K - 1]
while q:
	s = q.pop()
	for t in T[s]:
		if not L[t[0]][1]:
			L[t[0]][0] = L[s][0] + t[1]
			L[t[0]][1] = 1
			q.append(t[0])
for q in range(Q):
	[x, y] = [int(x) for x in input().split()]
	print(L[x - 1][0] + L[y - 1][0])


import sys
sys.setrecursionlimit(200000)
n = int(input())
l = [list(map(int, input().split())) for _ in range(n - 1)]
(q, k) = list(map(int, input().split()))
k -= 1
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])


import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
tree = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b, c) = list(map(int, input().split()))
	tree[a - 1].append([b - 1, c])
	tree[b - 1].append([a - 1, c])
(Q, K) = list(map(int, input().split()))
dist = [-1] * N

def dfs(v, total_cost):
	dist[v] = total_cost
	for (v_next, cost) in tree[v]:
		if dist[v_next] >= 0:
			continue
		dfs(v_next, total_cost + cost)
dfs(K - 1, 0)
for i in range(Q):
	(x, y) = list(map(int, input().split()))
	print(dist[x - 1] + dist[y - 1])


def resolve():
	INF = 1 << 60
	N = int(input())
	G = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b, c) = [int(x) - 1 for x in input().split()]
		G[a].append((b, c + 1))
		G[b].append((a, c + 1))
	(Q, K) = list(map(int, input().split()))
	K -= 1
	dist = [INF] * N
	dist[K] = 0
	stack = []
	stack.append(K)
	while stack:
		v = stack.pop()
		for (to, c) in G[v]:
			if dist[to] <= dist[v] + c:
				continue
			dist[to] = dist[v] + c
			stack.append(to)
	for _ in range(Q):
		(x, y) = [int(x) - 1 for x in input().split()]
		print(dist[x] + dist[y])

def __starting_point():
	resolve()
__starting_point()


def main():
	N = int(input())
	adj = [[] for _ in range(N)]
	node = [0] * N
	for _ in range(N - 1):
		(a, b, c) = list(map(int, input().split()))
		adj[a - 1].append((b - 1, c))
		adj[b - 1].append((a - 1, c))
	(Q, K) = list(map(int, input().split()))
	K -= 1
	from collections import deque
	que = deque([K])
	check = set([K])
	for _ in range(N * 2):
		u = que.popleft()
		for (v, c) in adj[u]:
			if v in check:
				continue
			node[v] = node[u] + c
			que.append(v)
			check.add(v)
		if len(que) == 0:
			break
	for _ in range(Q):
		(x, y) = list(map(int, input().split()))
		ans = node[x - 1] + node[y - 1]
		print(ans)

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 8)
N = int(input())
vertex = [{} for _ in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	vertex[a - 1][b - 1] = c
	vertex[b - 1][a - 1] = c
(Q, K) = map(int, input().split())
d = [0 for i in range(N)]

def dfs(v1, v2):
	d[v2] = d[v1] + vertex[v1][v2]
	for v in vertex[v2]:
		if v == v1:
			continue
		dfs(v2, v)
for v in vertex[K - 1].keys():
	dfs(K - 1, v)
for q in range(Q):
	(x, y) = map(int, input().split())
	print(d[x - 1] + d[y - 1])


import sys
sys.setrecursionlimit(1000000)
n = int(input())
ablist = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	ablist[a - 1].append((b - 1, c))
	ablist[b - 1].append((a - 1, c))
(q, k) = map(int, input().split())
depth = [-1 for _ in range(n)]

def dfs(v, p, d):
	depth[v] = d
	for (to, c) in ablist[v]:
		if to == p:
			continue
		dfs(to, v, d + c)
dfs(k - 1, -1, 0)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(depth[x - 1] + depth[y - 1])


import networkx as nx
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)]
G = nx.Graph()
for (a, b, c) in ABC:
	G.add_edge(a - 1, b - 1, weight=c)
(pred, dist) = nx.dijkstra_predecessor_and_distance(G, K - 1)
for (x, y) in XY:
	print(dist[x - 1] + dist[y - 1])


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, bisect
from operator import itemgetter
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
stdin = sys.stdin
ni = lambda : int(ns())
nf = lambda : float(ns())
na = lambda : list(map(int, stdin.readline().split()))
nb = lambda : list(map(float, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()

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 adj[v]:
			if seen[to] == False and dist[v] + cost < dist[to]:
				dist[to] = dist[v] + cost
				heappush(hq, (dist[to], to))
	return dist
N = ni()
adj = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = na()
	adj[a - 1].append((b - 1, c))
	adj[b - 1].append((a - 1, c))
(Q, K) = na()
ans = []
d = dijkstra(K - 1, N)
for i in range(Q):
	(x, y) = na()
	x -= 1
	y -= 1
	ans.append(d[x] + d[y])
for i in range(Q):
	print(ans[i])


from collections import deque
n = int(input())
num = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b, c) = list(map(int, input().split()))
	num[a - 1].append([b, c])
	num[b - 1].append([a, c])
(q, k) = list(map(int, input().split()))
seen = [False] * n
queue = deque()
queue.append(k)
ans = [0] * n
seen[k - 1] = True
for i in range(n):
	if len(queue) == 0:
		break
	num1 = queue.popleft()
	for j in range(len(num[num1 - 1])):
		num2 = num[num1 - 1][j][0]
		if seen[num2 - 1] == False:
			queue.append(num2)
			seen[num2 - 1] = True
			ans[num2 - 1] = ans[num1 - 1] + num[num1 - 1][j][1]
for i in range(q):
	(x, y) = list(map(int, input().split()))
	print(ans[x - 1] + ans[y - 1])


from collections import deque

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


import sys
sys.setrecursionlimit(1145141919)
N = int(input())
d = [-1 for _ in range(N + 1)]
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	e[a].append((b, c))
	e[b].append((a, c))
(Q, K) = map(int, input().split())

def dfs(now, dis):
	d[now] = dis
	for (nxt, cos) in e[now]:
		if d[nxt] == -1:
			dfs(nxt, dis + cos)
dfs(K, 0)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(d[x] + d[y])


import sys, math, collections, itertools
input = sys.stdin.readline
N = int(input())
tree = [[] for i in range(N + 1)]
for _ 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()))
memo = [-1] * (N + 1)
q = collections.deque([K])
memo[K] = 0
while q:
	now = q.pop()
	for (direct, cost) in tree[now]:
		if memo[direct] == -1:
			memo[direct] = memo[now] + cost
			q.append(direct)
for _ in range(Q):
	(a, b) = list(map(int, input().split()))
	ans = memo[a] + memo[b]
	print(ans)


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
	(u, v, c) = map(int, input().split())
	e[u].append((v, c))
	e[v].append((u, c))
(Q, K) = map(int, input().split())
dp = [10 ** 15] * (N + 1)
dp[K] = 0
s = [K]
while len(s):
	x = s.pop()
	for (y, d) in e[x]:
		if dp[y] > dp[x] + d:
			s.append(y)
			dp[y] = dp[x] + d
for _ in range(Q):
	(u, v) = map(int, input().split())
	print(dp[u] + dp[v])


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


import sys
sys.setrecursionlimit(10 ** 6)

def dfs_rec(start, prev, c):
	cost[start] = cost[prev] + c
	for (node, c) in tr[start]:
		if node != prev:
			dfs_rec(node, start, c)
	return
n = int(input())
tr = [[] for i in range(n)]
cost = [0] * n
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	tr[a - 1].append([b - 1, c])
	tr[b - 1].append([a - 1, c])
(q, k) = map(int, input().split())
dfs_rec(k - 1, k - 1, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	print(cost[x - 1] + cost[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)
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)]
G = [[] * N for _ in range(N)]
for (a, b, c) in ABC:
	G[a - 1].append((b - 1, c))
	G[b - 1].append((a - 1, c))
D = [-1] * N

def dfs(v, d):
	D[v] = d
	for (i, c) in G[v]:
		if D[i] < 0:
			dfs(i, d + c)
dfs(K - 1, 0)
for (x, y) in XY:
	print(D[x - 1] + D[y - 1])


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())
k = k - 1
stack = [k]
dis = [-1] * n
dis[k] = 0
while stack != []:
	new = []
	for j in stack:
		d = dis[j]
		for i in G[j]:
			if dis[i[0]] == -1:
				dis[i[0]] = d + i[1]
				new.append(i[0])
	stack = new
for i in range(q):
	(x, y) = map(int, input().split())
	x = x - 1
	y = y - 1
	print(dis[x] + dis[y])


import sys
sys.setrecursionlimit(10 ** 9)
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])
(q, k) = map(int, input().split())
check = [False for _ in range(n)]
dist = [0 for _ in range(n)]

def dfs(pos, b_pos):
	for (n_pos, c) in edges[pos]:
		if n_pos == b_pos:
			continue
		check[n_pos] = True
		dist[n_pos] = c + dist[pos]
		dfs(n_pos, pos)
check[k - 1] = True
dfs(k - 1, -1)
for _ in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(dist[x] + dist[y])


import sys
import itertools
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(input())
adj = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b, c) = list(map(int, input().split()))
	a -= 1
	b -= 1
	adj[a].append((c, b))
	adj[b].append((c, a))
(Q, K) = list(map(int, input().split()))
K -= 1

def dijkstra(start):
	dist = [INF for _ in range(N)]
	visited = [False for _ in range(N)]
	q = [(0, start)]
	dist[start] = 0
	while len(q) > 0:
		v = heapq.heappop(q)
		a = v[1]
		if visited[a]:
			continue
		visited[a] = True
		for u in adj[a]:
			w = u[0]
			b = u[1]
			if dist[a] + w < dist[b]:
				dist[b] = dist[a] + w
				heapq.heappush(q, (dist[b], b))
	return dist
dist = dijkstra(K)
for i in range(Q):
	(x, y) = list(map(int, input().split()))
	x -= 1
	y -= 1
	print(dist[x] + dist[y])


N = int(input())
E = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	E[a].append((b, c))
	E[b].append((a, c))
(Q, K) = map(int, input().split())
K = K - 1
D = [-1] * N
D[K] = 0
q = [(K, 0)]
while q:
	(k, d) = q.pop()
	for (n, c) in E[k]:
		if D[n] < 0:
			D[n] = d + c
			q.append((n, d + c))
for i in range(Q):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	r = D[x] + D[y]
	print(r)


def main():
	n = int(input())
	G = {}
	for i in range(n):
		G[i + 1] = []
	for _ in range(n - 1):
		(a, b, c) = list(map(int, input().split()))
		G[a] += [[b, c]]
		G[b] += [[a, c]]
	(q, k) = list(map(int, input().split()))
	dist = [-1] * n
	dist[k - 1] = 0
	que = [k]
	while len(que) > 0:
		s = que.pop(0)
		for [nv, c] in G[s]:
			if dist[nv - 1] != -1:
				continue
			dist[nv - 1] = dist[s - 1] + c
			que.append(nv)
	for _ in range(q):
		(x, y) = list(map(int, input().split()))
		print(dist[x - 1] + dist[y - 1])

def __starting_point():
	main()
__starting_point()


import networkx as nx
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)]
G = nx.Graph()
for (a, b, c) in ABC:
	G.add_edge(a - 1, b - 1, weight=c)
dist = nx.shortest_path_length(G, K - 1, weight='weight', method='bellman-ford')
for (x, y) in XY:
	print(dist[x - 1] + dist[y - 1])


import sys
import heapq
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
in_n = lambda : int(readline())
in_nn = lambda : list(map(int, readline().split()))
in_nl = lambda : list(map(int, readline().split()))
in_na = lambda : list(map(int, read().split()))
in_s = lambda : readline().rstrip().decode('utf-8')
INF = 10 ** 18

def dijkstra(N, s0, edge):
	d = [INF] * N
	used = [False] * N
	edgelist = [(0, s0)]
	heapq.heapify(edgelist)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = True
		for e in edge[v]:
			if d[e[1]] <= e[0] + d[v] or used[e[1]]:
				continue
			heapq.heappush(edgelist, [e[0] + d[v], e[1]])
	return d

def main():
	N = in_n()
	edge = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b, c) = in_nn()
		(a, b) = (a - 1, b - 1)
		edge[a].append((c, b))
		edge[b].append((c, a))
	(Q, K) = in_nn()
	d = dijkstra(N, K - 1, edge)
	ans = []
	for i in range(Q):
		(x, y) = in_nn()
		(x, y) = (x - 1, y - 1)
		ans.append(d[x] + d[y])
	print('\n'.join(map(str, ans)))

def __starting_point():
	main()
__starting_point()


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	N = I()
	G = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b, c) = LI()
		G[a - 1].append((b - 1, c))
		G[b - 1].append((a - 1, c))
	(Q, K) = LI()
	K -= 1
	dist = [-1] * N
	dist[K] = 0
	que = collections.deque()
	que.append(K)
	while que:
		c = que.popleft()
		for (n, l) in G[c]:
			if dist[n] == -1:
				dist[n] = dist[c] + l
				que.append(n)
	for _ in range(Q):
		(x, y) = LI_()
		ans = dist[x] + dist[y]
		print(ans)

def __starting_point():
	resolve()
__starting_point()


N = int(input())
E = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	E[a].append((b, c))
	E[b].append((a, c))
(Q, K) = 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) = map(int, input().split())
	print(costs[x - 1] + costs[y - 1])


from collections import deque
N = int(input())
adj = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	adj[a].append((b, c))
	adj[b].append((a, c))
(Q, K) = map(int, input().split())
d = [-1 for i in range(N + 1)]
q = deque()
q.append(K)
d[K] = 0
while q:
	u = q.popleft()
	for (v, c) in adj[u]:
		if d[v] == -1:
			d[v] = d[u] + c
			q.append(v)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(d[x] + d[y])


import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
NODES = {}
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	if not a in NODES:
		NODES[a] = []
	if not b in NODES:
		NODES[b] = []
	NODES[a].append((b, c))
	NODES[b].append((a, c))
(Q, K) = map(int, input().split())
MP = [-1] * (N + 1)
MP[K] = 0

def dfs(k):
	for (i, c) in NODES[k]:
		if MP[i] == -1:
			MP[i] = MP[k] + c
			dfs(i)
dfs(K)
for (l, r) in [tuple(map(int, input().split())) for _ in range(Q)]:
	print(MP[l] + MP[r])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	edge[a].append((b, c))
	edge[b].append((a, c))
(Q, K) = map(int, input().split())
dist = [None] * (N + 1)

def set_dist(x, d):
	dist[x] = d
	for (y, dd) in edge[x]:
		if dist[y] is not None:
			continue
		set_dist(y, d + dd)
set_dist(K, 0)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(dist[x] + dist[y])


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
INF = 9999999999
d = [INF for _ in range(n)]
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])

def dfs(v, p, dv):
	d[v] = dv
	for (gi, c) in g[v]:
		if gi == p:
			continue
		dfs(gi, v, dv + c)
(q, k) = map(int, input().split())
dfs(k - 1, -1, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	print(d[x - 1] + d[y - 1])


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


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


import sys
sys.setrecursionlimit(pow(10, 6))
readline = sys.stdin.readline

def dfs(nw, d):
	V[nw] = d
	for nx in G[nw]:
		if V[nx[0]] == -1:
			dfs(nx[0], d + nx[1])
n = int(readline())
G = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, readline().split())
	G[a - 1].append((b - 1, c))
	G[b - 1].append((a - 1, c))
(q, k) = map(int, readline().split())
V = [-1] * n
dfs(k - 1, 0)
for i in range(q):
	(x, y) = map(lambda x: int(x) - 1, readline().split())
	print(V[x] + V[y])


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

def BFS(K, edges, N):
	roots = [[] for i in range(N)]
	for (a, b, c) in edges:
		roots[a - 1] += [(b - 1, c)]
		roots[b - 1] += [(a - 1, 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
(Q, K) = map(int, input().split())
K = K - 1
dist = BFS(K, edges, N)
lsxy = []
for i in range(Q):
	(x, y) = map(int, input().split())
	x = x - 1
	y = y - 1
	lsxy.append([x, y])
for i in lsxy:
	print(dist[i[0]] + dist[i[1]])


n = int(input())
V = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	V[a].append([b, c])
	V[b].append([a, c])
(q, k) = map(int, input().split())
from collections import deque
dis = [-1] * (n + 1)
Q = deque([])
Q.append(k)
dis[k] = 0
while Q:
	r = Q.popleft()
	for (A, D) in V[r]:
		if dis[A] == -1:
			Q.append(A)
			dis[A] = dis[r] + D
x = [0] * q
for i in range(q):
	(x, y) = map(int, input().split())
	print(dis[x] + dis[y])


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
route = [[] for _ in range(n)]
distance = [-1 for _ in range(n)]
INF = float('inf')
for _ in range(n - 1):
	(a, b, c) = list(map(int, input().split()))
	route[a - 1].append((b - 1, c))
	route[b - 1].append((a - 1, c))
(q, k) = list(map(int, input().split()))

def Tree(s, g, c):
	distance[s] = c
	for (g1, val) in route[s]:
		if g == g1:
			continue
		Tree(g1, s, c + val)

def TransitTreePath():
	Tree(k - 1, -1, 0)
	for _ in range(q):
		(x, y) = list(map(int, input().split()))
		ans = distance[x - 1] + distance[y - 1]
		print(ans)

def __starting_point():
	TransitTreePath()
__starting_point()


from collections import defaultdict, deque
import sys
finput = lambda : sys.stdin.readline().strip()

def main():
	n = int(finput())
	edges = [tuple(map(int, finput().split())) for _ in range(n - 1)]
	(q, k) = list(map(int, finput().split()))
	xy = [tuple(map(int, finput().split())) for _ in range(q)]
	ed = defaultdict(deque)
	wt = defaultdict(int)
	for e in edges:
		ed[e[0]].append(e[1])
		ed[e[1]].append(e[0])
		wt[e[0], e[1]] = e[2]
		wt[e[1], e[0]] = e[2]
	stack = deque([k])
	cv = stack[0]
	dist = defaultdict(int)
	while stack:
		while ed[cv]:
			if cv != k:
				if ed[cv][-1] == stack[-1]:
					ed[cv].pop()
					if not ed[cv]:
						break
			stack.append(cv)
			cv = ed[cv].pop()
			dist[cv] = dist[stack[-1]] + wt[stack[-1], cv]
		cv = stack.pop()
	for que in xy:
		print(dist[que[0]] + dist[que[1]])

def __starting_point():
	main()
__starting_point()


from collections import deque
n = int(input())
e = [[] for _ in range(n + 1)]
dist = [-1] * (n + 1)
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	e[a].append((b, c))
	e[b].append((a, c))
(q, k) = map(int, input().split())
a = deque()
a.append((k, 0))
while a:
	(x, d) = a.popleft()
	dist[x] = d
	for (j, nc) in e[x]:
		if dist[j] != -1:
			continue
		else:
			a.append((j, d + nc))
ans = []
for i in range(q):
	(x, y) = map(int, input().split())
	ans.append(dist[x] + dist[y])
print(*ans, sep='\n')


from collections import deque
N = int(input())
E = {i: {} for i in range(1, N + 1)}
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	E[a][b] = c
	E[b][a] = c
(Q, K) = map(int, input().split())
inf = float('inf')
Dist = [inf] * (N + 1)
Dist[K] = 0
X = deque([K])
while X:
	u = X.popleft()
	for v in E[u]:
		if Dist[v] == inf:
			X.append(v)
			Dist[v] = Dist[u] + E[u][v]
T = [0] * Q
for i in range(Q):
	(x, y) = map(int, input().split())
	T[i] = Dist[x] + Dist[y]
print('\n'.join(map(str, T)))


n = int(input())
path = [[] for i in range(n)]
for i 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())
distance = [None] * n
distance[k - 1] = 0
queue = [k - 1]
while len(queue):
	p = queue.pop()
	for (i, c) in path[p]:
		if distance[i] == None:
			distance[i] = distance[p] + c
			queue.append(i)
for i in range(q):
	(x, y) = map(int, input().split())
	print(distance[x - 1] + distance[y - 1])


import sys
import queue
n = int(input())
clis = [[] for i in range(n)]
for i in range(n - 1):
	(ai, bi, ci) = map(int, input().split())
	clis[ai - 1].append([bi, ci])
	clis[bi - 1].append([ai, ci])
(q, k) = map(int, input().split())
xy = []
for i in range(q):
	xy.append(list(map(int, input().split())))
distance = [0 for i in range(n)]
seen = [0 for i in range(n)]
que = queue.Queue()
que.put(k)
seen[k - 1] = 1
while not que.empty():
	c = que.get()
	for (aa, cc) in clis[c - 1]:
		if seen[aa - 1] == 0:
			distance[aa - 1] = distance[c - 1] + cc
			seen[aa - 1] = 1
			que.put(aa)
for i in range(q):
	print(distance[xy[i][0] - 1] + distance[xy[i][1] - 1])


import sys
sys.setrecursionlimit(1000000)
n = int(input())
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	tree[a].append([b, c])
	tree[b].append([a, c])
(q, k) = map(int, input().split())
d = [0] * (n + 1)

def dfs(x, c, p):
	global tree
	d[x] = c
	for (l, c_) in tree[x]:
		if l == p:
			continue
		else:
			dfs(l, c_ + c, x)
dfs(k, 0, -1)
for i in range(q):
	(a, b) = map(int, input().split())
	print(d[a] + d[b])


from collections import deque
N = int(input())
g = [[] for x in range(N + 1)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	g[a].append([b, c])
	g[b].append([a, c])
(Q, K) = map(int, input().split())
d = [-1] * (N + 1)
d[K] = 0
r = deque()
r.append(K)
while len(r) > 0:
	i = r.popleft()
	for v in g[i]:
		if d[v[0]] == -1:
			d[v[0]] = d[i] + v[1]
			r.append(v[0])
q = list()
for i in range(Q):
	q.append(input())
for i in range(Q):
	(x, y) = map(int, q[i].split())
	print(d[x] + d[y])


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


import sys
sys.setrecursionlimit(10000000)
n = int(input())
s = [[] for i in range(n + 1)]
g = [0] * (n + 1)
h = [True] * (n + 1)
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	s[a].append([b, c])
	s[b].append([a, c])

def dfs(x):
	h[x] = False
	for i in s[x]:
		if h[i[0]]:
			g[i[0]] = g[x] + i[1]
			dfs(i[0])
(q, k) = map(int, input().split())
dfs(k)
for i in range(q):
	(x, y) = map(int, input().split())
	print(g[x] + g[y])


from collections import deque
n = int(input())
e = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	e[a].append((b, c))
	e[b].append((a, c))
(Q, k) = map(int, input().split())
k -= 1
d = [-1] * n
d[k] = 0
q = deque([])
q.append(k)
while q:
	now = q.popleft()
	for (nex, dis) in e[now]:
		if d[nex] == -1:
			d[nex] = d[now] + dis
			q.append(nex)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(d[x - 1] + d[y - 1])


def main():
	from collections import defaultdict
	from heapq import heappop, heappush
	N = int(input())
	edge = defaultdict(list)
	length = defaultdict(lambda : defaultdict(lambda : 10 ** 20))
	for i in range(N - 1):
		(a, b, c) = map(int, input().split())
		a -= 1
		b -= 1
		edge[a].append(b)
		edge[b].append(a)
		if b < a:
			(a, b) = (b, a)
		length[a][b] = c
	(Q, K) = map(int, input().split())
	K -= 1
	cost = [0] * N
	length[K][K] = 0
	targets = [(0, K)]
	cost = [10 ** 18] * N
	cost[K] = 0
	visited = [False] * N
	while targets:
		(c, t) = heappop(targets)
		if visited[t]:
			continue
		cost[t] = c
		visited[t] = True
		for v in edge[t]:
			if cost[v] > cost[t] + length[min(t, v)][max(t, v)]:
				heappush(targets, (cost[t] + length[min(t, v)][max(t, v)], v))
	out = []
	for i in range(Q):
		(x, y) = map(lambda x: int(x) - 1, input().split())
		out.append(cost[x] + cost[y])
	print('\n'.join(map(str, out)))
main()


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
l = [-1] * N
tree = [[] for i in range(N)]
for i in range(N - 1):
	(A, B, C) = list(map(int, input().split()))
	A -= 1
	B -= 1
	tree[A].append((B, C))
	tree[B].append((A, C))
(Q, V) = list(map(int, input().split()))

def DFS(now, past, dis):
	l[now] = dis
	for i in tree[now]:
		if i[0] == past:
			continue
		elif l[i[0]] == -1:
			DFS(i[0], now, dis + i[1])
DFS(V - 1, -1, 0)
for i in range(Q):
	(s, e) = list(map(int, input().split()))
	s -= 1
	e -= 1
	print(l[s] + l[e])


from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	edges[a].append((b, c))
	edges[b].append((a, c))
dp = [0] * (N + 1)
(Q, K) = map(int, input().split())
que = deque()
que.append((K, 0))
path = {}
while que:
	(now, cost) = que.pop()
	path[now] = ''
	dp[now] = cost
	for (x, c) in edges[now]:
		if x not in path:
			que.append((x, cost + c))
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(dp[x] + dp[y])


import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
(T, D) = ({i: [] for i in range(N)}, [-1] * N)
for _ 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))

def dfs(p, c, d):
	D[c] = d
	for (c2, d2) in T[c]:
		if c2 != p:
			dfs(c, c2, d + d2)
(Q, K) = map(int, input().split())
dfs(-1, K - 1, 0)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(D[x - 1] + D[y - 1])


from heapq import heappush, heappop

def resolve():
	INF = 1 << 60
	N = int(input())
	G = [[] for _ in range(N)]
	for _ in range(N - 1):
		(a, b, c) = [int(x) - 1 for x in input().split()]
		G[a].append((b, c + 1))
		G[b].append((a, c + 1))
	(Q, K) = list(map(int, input().split()))
	K -= 1
	dist = [INF] * N
	hq = []
	heappush(hq, (K, 0))
	dist[K] = 0
	while hq:
		(v, cost) = heappop(hq)
		for (to, c) in G[v]:
			if dist[to] <= dist[v] + c:
				continue
			dist[to] = dist[v] + c
			heappush(hq, (to, dist[to]))
	for _ in range(Q):
		(x, y) = [int(x) - 1 for x in input().split()]
		print(dist[x] + dist[y])

def __starting_point():
	resolve()
__starting_point()


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


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
n = int(input())
edges = [[] for i in range(n)]
dis = [-1] * n
for _ in range(n - 1):
	(a, s, d) = map(int, input().split())
	a -= 1
	s -= 1
	edges[a].append((s, d))
	edges[s].append((a, d))
(q, k) = map(int, input().split())
dis[k - 1] = 0

def dfs(now):
	for (i, d) in edges[now]:
		if dis[i] == -1:
			dis[i] = dis[now] + d
			dfs(i)
dfs(k - 1)
for _ in range(q):
	(a, s) = map(int, input().split())
	print(dis[a - 1] + dis[s - 1])


from collections import deque
N = int(input())
ARR = [list(map(int, input().split())) for i in range(N - 1)]
(Q, K) = map(int, input().split())
BRR = [list(map(int, input().split())) for i in range(Q)]

def prepare(n, arr):
	links = {}
	nodeStatus = {}
	distances = {}
	finalDistance = {}
	for i in range(1, N + 1):
		nodeStatus.__setitem__(i, False)
		finalDistance.__setitem__(i, 0)
	for i in range(len(arr)):
		tmp = arr[i]
		startNode = tmp[0]
		endNode = tmp[1]
		distance = tmp[2]
		distances.__setitem__((startNode, endNode), distance)
		distances.__setitem__((endNode, startNode), distance)
		if links.get(startNode) == None:
			links.__setitem__(startNode, [endNode])
		else:
			tmpChild = links.get(startNode)
			tmpChild.append(endNode)
			links.__setitem__(startNode, tmpChild)
		if links.get(endNode) == None:
			links.__setitem__(endNode, [startNode])
		else:
			tmpChild = links.get(endNode)
			tmpChild.append(startNode)
			links.setdefault(endNode, tmpChild)
	return (links, nodeStatus, distances, finalDistance)

def bfs(startNode):
	q = deque()
	q.append((startNode, 0))
	while len(q):
		(currentNode, dist) = q.popleft()
		finalDistance.__setitem__(currentNode, dist)
		nodeStatus.__setitem__(currentNode, True)
		childNodes = links.get(currentNode)
		for childNode in childNodes:
			if nodeStatus.get(childNode) == False:
				q.append((childNode, dist + distances.get((currentNode, childNode))))
(links, nodeStatus, distances, finalDistance) = prepare(N, ARR)
bfs(K)
for i in range(Q):
	dist1 = finalDistance[BRR[i][0]]
	dist2 = finalDistance[BRR[i][1]]
	print(dist1 + dist2)


import sys
sys.setrecursionlimit(1000000)
n = int(input())
tree = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	tree[a].append((b, c))
	tree[b].append((a, c))
depth = [0] * (n + 1)

def dfs(v, p, d):
	depth[v] = d
	for (to, cost) in tree[v]:
		if to != p:
			dfs(to, v, d + cost)
(q, k) = map(int, input().split())
dfs(k, 0, 0)
xy = [tuple(map(int, input().split())) for i in range(q)]
for (x, y) in xy:
	print(depth[x] + depth[y])


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


from collections import *
input = open(0).readline
n = int(input())
e = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	e[a - 1].append((b - 1, c))
	e[b - 1].append((a - 1, c))
(q, k) = map(int, input().split())
d = [0] * n
f = [0] * n
f[k - 1] = 1
s = deque([(k - 1, 0)])
while s:
	(t, c) = s.pop()
	f[t] = 1
	d[t] = c
	for (i, v) in e[t]:
		if not f[i]:
			s.append((i, v + c))
for _ in range(q):
	(x, y) = map(int, input().split())
	print(d[x - 1] + d[y - 1])


import sys
from collections import deque

def input():
	return sys.stdin.readline().strip()

def bfs(start):
	q = deque([start])
	dist = [-1] * (N + 1)
	dist[start] = 0
	while q:
		v = q.popleft()
		for (nv, nw) in g[v]:
			if dist[nv] > 0:
				continue
			dist[nv] = dist[v] + nw
			q.append(nv)
	return dist
N = int(input())
g = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = list(map(int, input().split()))
	g[a].append((b, c))
	g[b].append((a, c))
(Q, K) = list(map(int, input().split()))
d = bfs(K)
ans = []
for _ in range(Q):
	(x, y) = list(map(int, input().split()))
	print(d[x] + d[y])


n = int(input())
g = [[] for i in range(1 + n)]
v = [0] * (1 + n)
dist = [0] * (1 + n)
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	g[a].append([b, c])
	g[b].append([a, c])

def dfs(p):
	while p:
		(cur, depth) = p.pop()
		v[cur] = 1
		dist[cur] = depth
		for nb in g[cur]:
			if v[nb[0]] == 0:
				p.append([nb[0], depth + nb[1]])
	return
(q, k) = map(int, input().split())
dfs([[k, 0]])
for i in range(q):
	(x, y) = map(int, input().split())
	print(dist[x] + dist[y])


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
dct = defaultdict(list)
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	dct[a] += [[b, c]]
	dct[b] += [[a, c]]
(q, k) = map(int, input().split())
lk = [0] * n

def dfs(v, p, d):
	lk[v - 1] = d
	for l in dct[v]:
		if l[0] == p or lk[l[0] - 1] != 0:
			continue
		else:
			dfs(l[0], v, d + l[1])
	return
dfs(k, -1, 0)
for i in range(q):
	(x, y) = map(int, input().split())
	print(lk[x - 1] + lk[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n = int(input())
es = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	es[a].append((b, c))
	es[b].append((a, c))
ds = [0] * (n + 1)

def dfs(cur, prev, c):
	ds[cur] = ds[prev] + c
	for (e, c) in es[cur]:
		if e != prev:
			dfs(e, cur, c)
(q, k) = map(int, input().split())
dfs(k, k, 0)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(ds[x] + ds[y])


from collections import namedtuple, deque
N = int(input())
connection = [[] for _ in range(N)]
branch = namedtuple('branch', ['id', 'dist'])
for _ in range(N - 1):
	(a, b, c) = list(map(int, input().split()))
	connection[a - 1].append(branch(b - 1, c))
	connection[b - 1].append(branch(a - 1, c))
dist = [0] * N
(Q, K) = list(map(int, input().split()))
reserved = deque([K - 1])
seen = {K - 1}
while len(reserved) > 0:
	current = reserved.popleft()
	for next in connection[current]:
		if next.id in seen:
			continue
		seen.add(next.id)
		reserved.append(next.id)
		dist[next.id] = dist[current] + next.dist
Query = [list(map(int, input().split())) for _ in range(Q)]
for (x, y) in Query:
	print(dist[x - 1] + dist[y - 1])


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())
ds = [-1] * n
hq = [(0, k - 1)]
while hq:
	(c, idx) = heapq.heappop(hq)
	if ds[idx] != -1:
		continue
	ds[idx] = c
	for i in g[idx]:
		if ds[i[0]] == -1:
			heapq.heappush(hq, (i[1] + c, i[0]))
for i in range(q):
	(x, y) = map(int, input().split())
	print(ds[x - 1] + ds[y - 1])


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
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())
k -= 1
l = [0] * n

def dfs(a, b, c):
	for (i, j) in t[b]:
		if i != a:
			l[i] = c + j
			dfs(b, i, c + j)
dfs(-1, k, 0)
for _ in range(q):
	(x, y) = map(lambda x: int(x) - 1, input().split())
	print(l[x] + l[y])


import sys
sys.setrecursionlimit(1000000)
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))
(q, k) = map(int, input().split())
d = [-1] * n

def f(k, c):
	d[k] = c
	for (i, v) in g[k]:
		if d[i] == -1:
			f(i, c + v)
f(k - 1, 0)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(d[x - 1] + d[y - 1])


N = int(input())
abc = [tuple(map(int, input().split())) for i in range(N - 1)]
g = [set() for i in range(N)]
for (a, b, c) in abc:
	g[a - 1].add((b - 1, c))
	g[b - 1].add((a - 1, c))
memo = [-1] * N
(Q, K) = map(int, input().split())
import collections
q = collections.deque([(K - 1, 0)])
memo[K - 1] = 0
while q:
	(x, w) = q.popleft()
	for (a, b) in g[x]:
		if memo[a] == -1:
			memo[a] = w + b
			q.append((a, w + b))
for i in range(Q):
	(x, y) = map(int, input().split())
	print(memo[x - 1] + memo[y - 1])


from heapq import heappop, heappush
icase = 0
if icase == 0:
	n = int(input())
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(ai, bi, ci) = list(map(int, input().split()))
		g[ai - 1].append((bi - 1, ci))
		g[bi - 1].append((ai - 1, ci))
if icase == 1:
	n = 5
	g = [[(1, 1), (2, 1)], [(0, 1), (3, 1)], [(0, 1), (4, 1)], [(1, 1)], [(2, 1)]]
if icase == 2:
	n = 7
	g = [[(1, 1), (2, 3), (3, 5), (4, 7), (5, 9), (6, 11)], [(0, 1)], [(0, 3)], [(0, 5)], [(0, 7)], [(0, 9)], [(0, 11)]]
(q, k) = list(map(int, input().split()))
k = k - 1
hq = []
heappush(hq, (0, k))
inf = float('INF')
dist = [inf] * n
dist[k] = 0
while len(hq) > 0:
	(dd, state) = heappop(hq)
	for (v, dv) in g[state]:
		if dist[v] > dist[state] + dv:
			dist[v] = dist[state] + dv
			heappush(hq, (dist[v], v))
for i in range(q):
	(xi, yi) = list(map(int, input().split()))
	print(dist[xi - 1] + dist[yi - 1])


N = int(input())
way = [[] for _ in range(N + 1)]
depth = [float('inf')] * (N + 1)
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	way[a].append((b, c))
	way[b].append((a, c))
(Q, K) = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]
stack = []
stack.append((K, 0))
while stack:
	(now, d) = stack.pop()
	depth[now] = d
	for (i, j) in way[now]:
		if depth[i] < d + j:
			continue
		stack.append((i, d + j))
for (x, y) in xy:
	print(depth[x] + depth[y])


from collections import defaultdict, deque
import sys
finput = lambda : sys.stdin.readline().strip()

def main():
	n = int(finput())
	edges = [tuple(map(int, finput().split())) for _ in range(n - 1)]
	(q, k) = list(map(int, finput().split()))
	xy = [tuple(map(int, finput().split())) for _ in range(q)]
	stack = [-1] * (n + 1)
	stack[k] = 0
	ed = defaultdict(list)
	wt = defaultdict(int)
	for e in edges:
		ed[e[0]].append(e[1])
		ed[e[1]].append(e[0])
		wt[e[0], e[1]] = e[2]
		wt[e[1], e[0]] = e[2]
	ce = deque([(k, x) for x in ed[k]])
	ne = deque()
	while True:
		while ce:
			e = ce.pop()
			stack[e[1]] = stack[e[0]] + wt[e]
			for v in ed[e[1]]:
				if stack[v] < 0:
					ne.append((e[1], v))
		if not ne:
			break
		ce.extend(ne)
		ne.clear()
	for que in xy:
		print(stack[que[0]] + stack[que[1]])

def __starting_point():
	main()
__starting_point()


n = int(input())
l = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	l[a - 1] += [[b - 1, c]]
	l[b - 1] += [[a - 1, c]]
(q, k) = map(int, input().split())
k -= 1
Q = [[k, 0]]
c = [0] * n
c[k] = -1
while Q:
	p = []
	for (i, j) in Q:
		for (x, y) in l[i]:
			if c[x] == 0:
				c[x] = j + y
				p += [[x, c[x]]]
	Q = p
c[k] = 0
for i in range(q):
	(x, y) = map(int, input().split())
	print(c[x - 1] + c[y - 1])


import sys
from collections import deque
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	N = int(readline())
	G = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b, c) = map(int, readline().split())
		G[a - 1].append((b - 1, c))
		G[b - 1].append((a - 1, c))
	(Q, K, *XY) = map(int, read().split())
	K -= 1
	stack = deque([K])
	dist = [INF] * N
	dist[K] = 0
	while stack:
		v = stack.pop()
		for (nv, cost) in G[v]:
			if dist[nv] == INF:
				dist[nv] = dist[v] + cost
				stack.append(nv)
	ans = [0] * Q
	for (i, (x, y)) in enumerate(zip(*[iter(XY)] * 2)):
		ans[i] = dist[x - 1] + dist[y - 1]
	print(*ans, sep='\n')
	return

def __starting_point():
	main()
__starting_point()


N = int(input())
E = {i: [] for i in range(N + 1)}
for i in range(N - 1):
	(a, b, c) = [int(x) for x in input().split()]
	E[a].append([b, c])
	E[b].append([a, c])
(Q, K) = [int(x) for x in input().split()]
cost = [0] * (N + 1)
stk = [[K, -1, 0]]
while stk:
	(v, p, c) = stk.pop()
	if cost[v] != 0:
		continue
	cost[v] = c
	for (i, j) in E[v]:
		if i != p:
			stk.append([i, v, c + j])
for i in range(Q):
	(a, b) = [int(x) for x in input().split()]
	print(cost[a] + cost[b])


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

def dfs(v, p=-1, d=0):
	depth[v] = d
	for (i, j) in abc[v]:
		if i == p:
			continue
		dfs(i, v, d + j)
dfs(k)
queries = []
for _ in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(depth[x] + depth[y])


import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es = [[] for _ in range(n)]
d = [0] * n
used = [True] * n
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	es[a].append((b, c))
	es[b].append((a, c))

def dfs(s, dist):
	used[s] = False
	for (v, x) in es[s]:
		if used[v]:
			d[v] = dist + x
			dfs(v, dist + x)
(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])


from collections import deque
n = int(input())
g = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = [int(x) for x in input().split()]
	g[a].append((b, c))
	g[b].append((a, c))
(q, k) = [int(x) for x in input().split()]
d = [-1] * (n + 1)
d[k] = 0
pq = deque()
pq.append(k)
while len(pq):
	u = pq.popleft()
	for (v, w) in g[u]:
		if d[v] != -1:
			continue
		d[v] = d[u] + w
		pq.append(v)
for i in range(q):
	(u, v) = [int(x) for x in input().split()]
	print(d[u] + d[v])


import sys
sys.setrecursionlimit(10 ** 5 + 5)
N = int(input())
g = {i: [] for i in range(1, N + 1)}
for _ 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())
xy = []
for _ in range(Q):
	xy.append(tuple(map(int, input().split())))
d = [-1 for _ in range(N + 1)]

def dfs(s: int):
	for (v, c) in g[s]:
		if d[v] == -1:
			d[v] = d[s] + c
			dfs(v)
d[K] = 0
dfs(K)
for (x, y) in xy:
	print(d[x] + d[y])


import sys
sys.setrecursionlimit(200000)
N = int(input())
adj = {}
adj = {i + 1: [] for i in range(N)}
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	adj[a].append((b, c))
	adj[b].append((a, c))
dis = [0] * N

def dfs(k, u, d):
	dis[k - 1] = d
	for (p, pk_dis) in adj[k]:
		if p != u:
			dfs(p, k, d + pk_dis)
(Q, K) = map(int, input().split())
dfs(K, -1, 0)
for i in range(Q):
	(x, y) = map(int, input().split())
	print(dis[x - 1] + dis[y - 1])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
n = int(input())
g = [[] for _ in range(n)]
for _ 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
dist = [float('inf')] * n
dist[k] = 0

def dfs(s):
	for (v, c) in g[s]:
		if dist[v] == float('inf'):
			dist[v] = dist[s] + c
			dfs(v)
dfs(k)
for _ in range(q):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	print(dist[x] + dist[y])


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	graph[a - 1].append((b - 1, c))
	graph[b - 1].append((a - 1, c))
(Q, K) = map(int, input().split())
visited = [0 for _ in range(N)]

def DFS(a, b, c):
	for (i, j) in graph[b]:
		if i != a:
			visited[i] = c + j
			DFS(b, i, c + j)
DFS(-1, K - 1, 0)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(visited[x - 1] + visited[y - 1])


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


import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	G[a].append((b, c))
	G[b].append((a, c))
(Q, K) = map(int, input().split())
d = [-1] * (N + 1)

def dfs(v, c):
	d[v] = c
	for (nv, cost) in G[v]:
		if d[nv] == -1:
			dfs(nv, cost + c)
dfs(K, 0)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(d[x] + d[y])


n = int(input())
g = [[] for i in range(n)]
for _ in range(n - 1):
	(u, v, c) = map(int, input().split())
	g[u - 1].append((v - 1, c))
	g[v - 1].append((u - 1, c))
(Q, k) = map(int, input().split())
d = [-1] * n
d[k - 1] = 0
q = [k - 1]
while q:
	t = q.pop()
	for (x, cost) in g[t]:
		if d[x] == -1:
			d[x] = d[t] + cost
			q.append(x)
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(d[x - 1] + d[y - 1])


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
inf = float('inf')
road = [dict() for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	road[a][b] = c
	road[b][a] = c
(q, k) = map(int, input().split())
dfs = [inf] * (n + 1)
dfs[k] = 0

def dodfs(x):
	for i in road[x]:
		if dfs[i] == inf:
			dfs[i] = dfs[x] + road[x][i]
			dodfs(i)
	return
dodfs(k)
for _ in range(q):
	(x, y) = map(int, input().split())
	print(dfs[x] + dfs[y])