Buggy python submission (verdict: Runtime Error):
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())
dist = [-1] * N


def dfs(u, par, d):
    dist[u] = d
    for w, cost in G[u]:
        if w == par:
            continue
        dfs(w, u, d + cost)


dfs(K - 1, -1, 0)

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





Fixed submission:
from heapq import heappush, heappop
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())
    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] * N
d[K] = 0
que = [(0, K)]
while que:
    cost, v = heappop(que)
    if d[v] < cost:
        continue
    for w, c in G[v]:
        if d[v] + c < d[w]:
            d[w] = d[v] + c
            heappush(que, (d[w], w))

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

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
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())
    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] * N
d[K] = 0
for i in range(N):
    que = [(0, K)]
    while que:
        cost, v = heappop(que)
        if d[v] < cost:
            continue
        for w, c in G[v]:
            if d[v] + c < d[w]:
                d[w] = d[v] + c
                heappush(que, (d[w], w))

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


Fixed submission:
from heapq import heappush, heappop
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())
    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] * N
d[K] = 0
que = [(0, K)]
while que:
    cost, v = heappop(que)
    if d[v] < cost:
        continue
    for w, c in G[v]:
        if d[v] + c < d[w]:
            d[w] = d[v] + c
            heappush(que, (d[w], w))

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

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
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())
    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] * N
d[K] = 0
for i in range(N):
    que = [(0, K)]
    while que:
        cost, v = heappop(que)
        if d[v] < cost:
            continue
        for w, c in G[v]:
            if d[v] + c < d[w]:
                d[w] = d[v] + c
                heappush(que, (d[w], w))

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


Fixed submission:
from heapq import heappush, heappop
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())
    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] * N
d[K] = 0
que = [(0, K)]
while que:
    cost, v = heappop(que)
    if d[v] < cost:
        continue
    for w, c in G[v]:
        if d[v] + c < d[w]:
            d[w] = d[v] + c
            heappush(que, (d[w], w))

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

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
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())
    a, b = a - 1, b - 1
    G[a].append((b, c))
    G[b].append((a, c))

INF = float("inf")
d = [[INF] * N for i in range(N)]
for i in range(N):
    d[i][i] = 0
for i in range(N):
    que = [(0, i)]
    while que:
        cost, v = heappop(que)
        if d[i][v] < cost:
            continue
        for w, c in G[v]:
            if d[i][v] + c < d[i][w]:
                d[i][w] = d[i][v] + c
                heappush(que, (d[i][w], w))

Q, K = map(int, input().split())
K -= 1
for i in range(Q):
    x, y = map(int, input().split())
    print(d[x - 1][K] + d[y - 1][K])


Fixed submission:
from heapq import heappush, heappop
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())
    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] * N
d[K] = 0
que = [(0, K)]
while que:
    cost, v = heappop(que)
    if d[v] < cost:
        continue
    for w, c in G[v]:
        if d[v] + c < d[w]:
            d[w] = d[v] + c
            heappush(que, (d[w], w))

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