Buggy python submission (verdict: Runtime Error):
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=[0]*N
memo[K-1]=0
Q,K=map(int,input().split())
import collections
q=collections.deque([(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[a-1]+memo[b-1])

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

Buggy python submission (verdict: Time Limit Exceeded):
import collections
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

k = [set() for i in range(N)]
g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c
    k[a-1].add(b-1)
    k[b-1].add(a-1)
c = [-1]*N
reached = [0]*N
c[K-1] = 0
q = collections.deque([K])
reached[K-1] = 1
while(len(q) > 0):
    x = q.popleft()

    for y in k[x-1]:
        if not reached[y]:
            q.append(y+1)
            c[y] = c[x-1]+g[x-1][y]
            reached[y] = 1
for i in range(Q):
    x, y = map(int, input().split())
    print(c[x-1] + c[y-1])


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

Buggy python submission (verdict: Time Limit Exceeded):
import collections
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

Q, K = map(int, input().split())
xy = [map(int, input().split()) for i in range(Q)]
k = [set() for i in range(N)]
g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c
    k[a-1].add(b-1)
    k[b-1].add(a-1)
c = [-1]*N
reached = [0]*N
c[K-1] = 0
q = collections.deque([K])
reached[K-1] = 1
while(len(q) > 0):
    x = q.popleft()

    for y in k[x-1]:
        if not reached[y]:
            q.append(y+1)
            c[y] = c[x-1]+g[x-1][y]
            reached[y] = 1

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


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

Buggy python submission (verdict: Time Limit Exceeded):
import collections
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

Q, K = map(int, input().split())
xy = [map(int, input().split()) for i in range(Q)]
k = [set() for i in range(N)]
g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c
    k[a-1].add(b-1)
    k[b-1].add(a-1)
c = [10**9*N]*N
c[K-1] = 0
q = collections.deque([K])
while(len(q) > 0):
    x = q.popleft()

    for y in k[x-1]:
        if c[y] == (10**9*N):
            q.append(y+1)
        c[y] = min(c[x-1]+g[x-1][y], c[y])

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


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

Buggy python submission (verdict: Time Limit Exceeded):
import collections
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c

c = [10**9*N]*N
c[K-1] = 0
q = collections.deque([K])
while(len(q) > 0):
    x = q.popleft()

    for j in range(N):
        if g[x-1][j] != -1:
            if c[j] == (10**9*N):
                q.append(j+1)
            c[j] = min(c[x-1]+g[x-1][j], c[j])

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


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

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

g = [[10**9+1]*N for i in range(N)]

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

G = csgraph_from_dense(g, null_value=10**9+1)

g2 = dijkstra(G)
for x, y in xy:
    print(int(g2[x-1][K-1] + g2[K-1][y-1]))


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

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

g = [[10**9+1]*N for i in range(N)]

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

G = csgraph_from_dense(g, null_value=10**9+1)

g2 = dijkstra(G)
for x, y in xy:
    print(int(g2[x-1][K-1] + g2[K-1][y-1]))


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

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

g = [[10**9+1]*N for i in range(N)]

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

G = csgraph_from_dense(g, null_value=10**9+1)

g2 = floyd_warshall(G)
for x, y in xy:
    print(int(g2[x-1][K-1] + g2[K-1][y-1]))


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