Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
 
def bellman_ford(s):
	d = [float('inf')]*n # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(n):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == n-1:
			return -1
	return d

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

q,k = map(int,input().split())
l = bellman_ford(k-1)
for i in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])

Fixed submission:
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
for _ in range(q):
	x,y = map(int,input().split())
	print(dijkstra(x-1)[k-1] + dijkstra(k-1)[y-1])

Fixed submission:
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
 
def bellman_ford(s):
	d = [float('inf')]*n # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(n):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == n-1:
			return -1
	return d

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

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

Fixed submission:
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
 
def bellman_ford(s):
	d = [float('inf')]*n # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(n):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == n-1:
			return -1
	return d

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

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

Fixed submission:
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])

Buggy python submission (verdict: Runtime Error):
n = int(input())
 
def bellman_ford(s):
	d = [float('inf')]*10 # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(10):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == 9:
			return -1
	return d

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

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

Fixed submission:
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])

Buggy python submission (verdict: Runtime Error):
n = int(input())
 
def bellman_ford(s):
	d = [float('inf')]*10 # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(10):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == 9:
			return -1
	return d

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

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

Fixed submission:
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])