CodeEff/ECCO huggingface dataset:
# Original solution
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(eval(input()))
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=list(map(int,input().split()))
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=list(map(int,input().split()))
distance=BFS(K-1,path,N)
for i in range(Q):
  x,y=list(map(int,input().split()))
  print((distance[x-1]+distance[y-1]))

# Optimized solution
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(eval(input()))
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=list(map(int,input().split()))
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=list(map(int,input().split()))
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print((distance[xy[i][0]-1]+distance[xy[i][1]-1]))
# Original solution
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(eval(input()))
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=list(map(int,input().split()))
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=list(map(int,input().split()))
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print((distance[xy[i][0]-1]+distance[xy[i][1]-1]))

# Optimized solution
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(eval(input()))
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=list(map(int,input().split()))
  path[a-1].append((b-1,c))
  path[b-1].append((a-1,c))
Q,K=list(map(int,input().split()))
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print((distance[xy[i][0]-1]+distance[xy[i][1]-1]))
# Original solution
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  import queue
  dist=[-1]*N
  dist[K]=0
  que=queue.Queue()
  que.put(K)
  while que.qsize():
    label=que.get()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que.put(i)
  return dist
 
N=int(eval(input()))
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=list(map(int,input().split()))
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=list(map(int,input().split()))
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print((distance[xy[i][0]-1]+distance[xy[i][1]-1]))

# Optimized solution
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  from collections import deque
  dist=[-1]*N
  dist[K]=0
  que=[]
  que.append(K)
  while que:
    label=que.pop(-1)
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(eval(input()))
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=list(map(int,input().split()))
  path[a-1]+=[(b-1,c)]
  path[b-1]+=[(a-1,c)]
Q,K=list(map(int,input().split()))
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print((distance[xy[i][0]-1]+distance[xy[i][1]-1]))
# Original solution
from collections import deque
n=int(eval(input()))
con=[[] for _ in range(n)]
dist=[[None]*n for _ in range(n)]
dist_f_k=[0]*n

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

q,k=list(map(int,input().split()))
dist_f_k[k-1]=None
que=deque([(k-1,0)])
while que:
	cur,d=que.popleft()
	for nxt in con[cur]:
		if dist_f_k[nxt]==0:
			tmp=d+dist[cur][nxt]
			que.append((nxt,tmp))
			dist_f_k[nxt]=tmp

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

# Optimized solution
from collections import deque
n=int(eval(input()))
con=[[] for _ in range(n)]
dist_f_k=[0]*n

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

q,k=list(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=list(map(int,input().split()))
	print((dist_f_k[x-1]+dist_f_k[y-1]))
# Original solution
from collections import deque
n=int(eval(input()))
con=[[] for _ in range(n)]
dist_f_k=[0]*n

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

q,k=list(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=list(map(int,input().split()))
	print((dist_f_k[x-1]+dist_f_k[y-1]))

# Optimized solution
from collections import deque
n,*t=list(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]))
# Original solution
from collections import deque
def main():
    n=int(eval(input()))
    dis=[[10**20 for i in range(n)] for i in range(n)]
    g=[[] for i in range(n)]
    for _ in range(n-1):
        a,b,c = list(map(int,input().split()))
        g[a-1].append(b-1)
        g[b-1].append(a-1)
        dis[a-1][b-1] = c
        dis[b-1][a-1] = c
    q,k = list(map(int,input().split()))
    k-=1
    d=deque([k])
    f=[False for i in range(n)]
    dis[k][k]=0
    while d:
        s= d.popleft()
        f[s]= True
        for sg in g[s]:
            if not f[sg]:
                dis[k][sg]= dis[k][s]+dis[s][sg]
                d.append(sg)
    lq=[]
    for _ in range(q):
        lq.append(list(map(int,input().split())))
    for sq in lq:
        print((dis[k][sq[0]-1]+dis[k][sq[1]-1]))

main()

# Optimized solution
from collections import deque
import sys
sys.setrecursionlimit(10**7)
n=int(eval(input()))
d=[10**20 for i in range(n)] 
g=[[] for i in range(n)]
for _ 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()))
k-=1
f=[False for i in range(n)]
d[k]=0

def dfs(s,c):
    f[s]=True
    d[s]=c
    for sg in g[s]:
        if not f[sg[0]]:
            dfs(sg[0],c+sg[1])
dfs(k,0)

lq=[]
for _ in range(q):
    lq.append(list(map(int,input().split())))
for sq in lq:
    print((d[sq[0]-1]+d[sq[1]-1]))
# Original solution
import sys
def input():
    return sys.stdin.readline()[:-1]

n=int(input())
def warshall_floyd(d):
    for x in range(n):
        for y in range(n):
            for z in range(n):
                d[y][z] = min(d[y][z],d[y][x]+d[x][z])
    return d 

graph = [[float("inf")]*n for _ in range(n)]

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

for i in range(n):
    graph[i][i] = 0

G = warshall_floyd(graph)

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

print(*ans , sep="\n")


# Optimized solution
n=int(input())
def warshall_floyd(d,k):
    for x in range(n):
        for y in range(n):
            for z in range(n):
                d[y][z] = min(d[y][z],d[y][x]+d[x][z])
    return d[k-1]

graph = [[float("inf") for x in range(n)] for _ in range(n)]

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

for i in range(n):
    graph[i][i] = 0
q,k = map(int,input().split())
G = warshall_floyd(graph,k)
ans = []

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

print(*ans , sep="\n")
# Original solution
from collections import deque

def f(k,edge,n):
    root = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c = edge[i][0],edge[i][1],edge[i][2]
        root[a-1].append([b-1,c])
        root[b-1].append([a-1,c])
    
    que = deque()
    for l in root[k]:
        que.append(l)
    
    dist = [float("inf")]*n
    dist[k] = 0
    visited = [False]*n
    que = deque([k])

    while que:
        pos = que.popleft()
        if not visited[pos]:
            visited[pos] = True
        for x,y in root[pos]:
            if not visited[x]:
                dist[x] = dist[pos] + y
                visited[x] = True
                que.append(x)
    return dist

n = int(input())
edge = [list(map(int,input().split())) for _ in range(n-1)]

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

ans = []
d = f(k-1,edge,n)
for i in range(q):
    x,y = map(int,input().split())
    ans.append(d[x-1] + d[y-1])

print(*ans , sep = "\n")


# Optimized solution
from collections import deque

n = int(eval(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()))
dis = [float('inf')]*(n+1)
dis[k] = 0
que = deque(g[k])
while que:
    x,y  = que.popleft()
    if dis[x] == float('inf'):
        dis[x] = y
        for x_, y_ in g[x]:
            que.append((x_, dis[x]+y_))
    else:
        dis[x] = min(dis[x], y)

ans = []
for _ in range(q):
    x,y = list(map(int,input().split()))
    ans.append(dis[x] + dis[y])
for a in ans:
    print(a)
# Original solution
from collections import defaultdict
inf = float('inf')

def solve(graph, n, start_node):
  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis 
  return costs
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(eval(input()))
graph = defaultdict(list)
costs_dict = {}

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

costs = solve(graph, n, k)

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


# Optimized solution
from collections import deque


def dfs():
    dis_from_k = [float('inf') for _ in range(N+1)]
    q = deque()
    used = set()
    q.append([K, 0])
    used.add(K)

    while len(q) > 0:
        prv_node, prv_cost = q.pop()
        for node, cost in g[prv_node]:
            if node in used:
                continue
            dis_from_k[node] = min(dis_from_k[node], prv_cost + cost)
            q.append([node, prv_cost + cost])
            used.add(node)
    return dis_from_k


N = int(eval(input()))
g = {i: [] for i in range(1, 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()))
dis_from_k = dfs()

for _ in range(Q):
    x, y = list(map(int, input().split()))
    print((dis_from_k[x] + dis_from_k[y]))
# Original solution
import heapq
n = int(eval(input()))
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = list(map(int, input().split()))
    cost[From][To] = d
    cost[To][From] = d

q, k = list(map(int, input().split()))
dist = [float('inf') for _ in range(n+1)]
dist[k] = 0
next_v = [[0, k]]

while len(next_v):
    v = next_v[0][1]
    for i in range(n+1):
        if dist[i] > dist[v] + cost[v][i]:
            dist[i] = dist[v] + cost[v][i]
            heapq.heappush(next_v, [dist[i], i])
    heapq.heappop(next_v)

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

# Optimized solution
import heapq
def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

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

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


q, k = list(map(int, input().split()))
dist, _ = dijkstra(n, edges, k-1)

for _ in range(q):
    x, y = list(map(int, input().split()))
    print((dist[x-1] + dist[y-1]))
# Original solution
import heapq


N = int(eval(input()))
tree = {i+1:[] for i in range(N)}
route = [10**20 for i in range(N+1)]
visited = [False for i in range(N+1)]

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

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

route[K], visited[K] = 0, True
queue = tree[K]

while len(queue):
    c, r = heapq.heappop(queue)

    if not visited[r]:
         visited[r], route[r] = True, c
         for cost, next_r in tree[r]:
             if not visited[next_r]:
                 heapq.heappush(queue, (route[r]+cost, next_r))

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


# Optimized solution
import heapq

N = int(eval(input()))
graph = [[] for i in range(N+1)]
visited = [False] * (N+1)
cost = [10**20 for i in range(N+1)]

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

for cr in graph[K]:
    heapq.heappush(q, cr)
visited[K] = True
cost[K] = 0

while q:
    c, r = heapq.heappop(q)
    
    if not visited[r]:
        visited[r] = True
        cost[r] = c
        
        for c_n, r_n in graph[r]:
            if not visited[r_n]:
                heapq.heappush(q, (c+c_n, r_n))
                
for i in range(Q):
    x, y = list(map(int, input().split()))
    print((cost[x] + cost[y]))
# Original solution
N = int(eval(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)]

graph = [[] for _ in range(N)]
for i, (ai, bi, ci) in enumerate(abc):
    graph[ai - 1].append((bi - 1, ci))
    graph[bi - 1].append((ai - 1, ci))

import heapq
MY_INF = None
    
q = [(0, K - 1)]
d = [MY_INF] * N
d[K - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst, c_dst in graph[src]:
        dist_tmp = dist + c_dst
        if d[dst] == None or d[dst] > dist_tmp:
            d[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

for i, (xi, yi) in enumerate(xy):
    print((d[xi - 1] + d[yi - 1]))

# Optimized solution
N = int(eval(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)]

graph = [[] for _ in range(N)]
for ai, bi, ci in abc:
    graph[ai - 1].append((bi - 1, ci))
    graph[bi - 1].append((ai - 1, ci))

MY_INF = 10 ** 18
import heapq

q = [(0, K - 1)]
d = [MY_INF] * N
d[K - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst, c_tmp in graph[src]:
        dist_tmp = dist + c_tmp
        if d[dst] > dist_tmp:
            d[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

for xi, yi in xy:
    print((d[xi - 1] + d[yi - 1]))
# Original solution
n = int(eval(input()))
a = [[int(i) for i in input().split()] for i in range(n-1)]
q,k = (int(i) for i in input().split())
question = [[int(i) for i in input().split()] for i in range(q)]
x = []
for i in range(n):
	subx = []
	for j in range(n):
		subx.append(float("inf"))
	x.append(subx)
for i in range(n): x[i][i] = 0
for i in a: x[i[0]-1][i[1]-1],x[i[1]-1][i[0]-1] = i[2],i[2]
for p in range(n):
	for i in range(n):
		for j in range(n):
			x[i][j] = min(x[i][p]+x[p][j],x[i][j])
for i in question:
	print((x[i[0]-1][k-1]+x[k-1][i[1]-1]))

# Optimized solution
n = int(eval(input()))
a = [[int(i) for i in input().split()] for i in range(n-1)]
q,k = (int(i) for i in input().split())
question = [[int(i) for i in input().split()] for i in range(q)]
x,ans = [[] for i in range(n)],[False for i in range(n)]
for i in a:
	x[i[0]-1].append([i[1],i[2]])
	x[i[1]-1].append([i[0],i[2]])
visit = [False for i in range(n)]
visit[k-1],now = True,[k]
while now:
	p = now.pop()
	for i in x[p-1]:
		if not visit[i[0]-1]:
			visit[i[0]-1],ans[i[0]-1] = True,ans[p-1]+i[1]
			now.append(i[0])
for i in question:
	print((ans[i[0]-1]+ans[i[1]-1]))
# Original solution
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  #input = open(0).readline
  N = int(eval(input()))
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[p(a,b)] = c

  M, K = list(map(int, input().split()))
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[p(u,v)]
      Q.append(v)

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

main()
  
 

# Optimized solution
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  input = open(0).readline
  N = int(eval(input()))
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[(a,b)] = c
    C[(b,a)] = c

  M, K = list(map(int, input().split()))
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[(u,v)]
      Q.append(v)

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

main()
# Original solution
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  input = open(0).readline
  N = int(eval(input()))
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[(a,b)] = c
    C[(b,a)] = c

  M, K = list(map(int, input().split()))
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[(u,v)]
      Q.append(v)

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

main()
  
 

# Optimized solution
from collections import deque
import sys
def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  input = sys.stdin.readline
  N = int(eval(input()))
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[p(a,b)] = c

  M, K = list(map(int, input().split()))
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[p(u,v)]
      Q.append(v)

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

main()
# Original solution
import sys
input = sys.stdin.readline
n = int(eval(input()))
v = [[0]+[]*(n+1) for i in range(n+1)]
for i in range(n-1):
    a,b,c = list(map(int,input().split()))
    v[a].append([b,c])
    v[b].append([a,c])

q,k = list(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 = list(map(int,input().split()))
    print((v[x][0]+v[y][0]))

# Optimized solution
import sys
def main():
    input = sys.stdin.readline
    n = int(eval(input()))
    v = [[0]+[]*(n+1) for i in range(n+1)]
    for i in range(n-1):
        a,b,c = list(map(int,input().split()))
        v[a].append([b,c])
        v[b].append([a,c])

    q,k = list(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 = list(map(int,input().split()))
        print((v[x][0]+v[y][0]))

if __name__ == '__main__':
    main()
# Original solution
def dijkstra(s: int, n: int, w: int, cost: list) -> list:
    d = [float("inf")]*n
    used = [False]*n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i

        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j], d[v]+cost[v][j])

    return d

n = int(eval(input()))
t = [[float("inf")]*(n) for _ in range(n)]
for _ in range(n-1):
    a, b, c = list(map(int, input().split()))
    t[a-1][b-1] = c
    t[b-1][a-1] = c

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

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


# Optimized solution
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(eval(input()))
t = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = list(map(int, input().split()))
    a -= 1; b -= 1;
    t[a].append((b, c))
    t[b].append((a, c))

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

dist = [0]*n

dfs(k)

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