Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]
for _ in range(N-1):
    v, c, p = iter(queue.pop(0))
    shortest_path[v] = c
    queue += [[u, T[v][u] + c, v] for u in T[v].keys() if u != p]

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

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(Q):
    x, y = map(int, input().split())
    while len(queue) > 0 and (shortest_path[x] == 0 or shortest_path[y] == 0):
        v = queue.pop(0)
        shortest_path[v[0]] = v[1]
        queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]
    print(shortest_path[x] + shortest_path[y])

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Runtime Error):
N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(Q):
    x, y = map(int, input().split())
    while len(queue) > 0 or (shortest_path[x] != 0 and shortest_path[y] != 0):
        v = queue.pop(0)
        shortest_path[v[0]] = v[1]
        queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]
    print(shortest_path[x] + shortest_path[y])

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(N-1):
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]

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

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]

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

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [[] for i 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())
shortest_path = [0 for _ in range(N+1)]
queue = [t + [K] for t in T[K]]

while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u[0], u[1] + v[1], v[0]] for u in T[v[0]] if u[0] != v[2]]

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

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [[] for i 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())
shortest_path = [0 for _ in range(N+1)]
queue = [t + [K] for t in T[K]]

while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u[0], u[1] + v[1], v[0]] for u in T[v[0]] if u[0] != v[2]]

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

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [[] for i 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())
shortest_path = [0 for _ in range(N+1)]
queue = [t + [K] for t in T[K]]


for _ in range(Q):
    x, y = map(int, input().split())

    while len(queue) > 0 and (shortest_path[x] == 0 or shortest_path[y] ==0):
        v = queue.pop(0)
        shortest_path[v[0]] = v[1]
        for u in T[v[0]]:
            if u[0] != v[2]:
                queue.append([u[0], u[1] + v[1], v[0]])
    
    print(shortest_path[x] + shortest_path[y])

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [[] for i 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())
shortest_path = [0 for _ in range(N+1)]
queue = [t + [K] for t in T[K]]
while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    for u in T[v[0]]:
        if u[0] != v[2]:
            queue.append([u[0], u[1] + v[1], v[0]])

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

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [[] for i 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())
shortest_path = [0 for _ in range(N+1)]
V, queue = set([K]), T[K]
while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    for u in T[v[0]]:
        if u[0] not in V:
            queue.append([u[0], u[1] + v[1]])
    V.add(v[0])

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

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
T = [[] for i 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())
shortest_path = [0 for _ in range(N+1)]
V, queue = set([K]), T[K]
while len(queue) > 0:
    v = queue.pop(queue.index(min(queue, key = lambda x: x[1])))
    shortest_path[v[0]] = v[1]
    for u in T[v[0]]:
        if u[0] not in V:
            queue.append([u[0], u[1] + v[1]])
    V.add(v[0])

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

Fixed submission:
from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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