Buggy python submission (verdict: Time Limit Exceeded):
import sys
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = coo_matrix((d, (i, j)),(N, N)).tocsc()

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = coo_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from scipy.sparse import csc_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = csc_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import dijkstra

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

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Fixed submission:
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])

Buggy python submission (verdict: Runtime Error):
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])

Fixed submission:
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])

Buggy python submission (verdict: Runtime Error):
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, p, d):
  D[v] = d
  for i, c in G[v]:
    if D[i] < 0:
      if i == p:
        continue
      dfs(i, v, d + c)

dfs(K - 1, -1, 0)

for x, y in XY:
  print(D[x - 1] + D[y - 1])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
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 = [[0] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c

D = [-1] * N
D[K - 1] = 0

q = deque()
q.append(K - 1)
while q:
  n = q.popleft()
  for i in range(N):
    if G[n][i] != 0 and D[i] < 0:
      q.append(i)
      D[i] = D[n] + G[n][i]

for x, y in XY:
  print(D[x - 1] + D[y - 1])

Fixed submission:
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])