Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


def solve(N, K, adj, queries):
    WHITE, GRAY, BLACK = 0, 1, 2

    num_of_nodes = N+1
    color = [WHITE] * num_of_nodes  # 各ノードの訪問状態
    d = [float('inf')] * num_of_nodes  # 始点からの重み

    # dijkstra(self, start):
    d[K] = 0
    pq = [(0, K)]

    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue

        for v, c in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heappush(pq, (d[v], v))
                color[v] = GRAY

    # 結果の表示
    for x, y in queries:
        print(d[x] + d[y])



def main():
    # データの入力
    N = int(input())
    adj = [[] for _ in range(N+1)]
    for i in range(N-1):
        f, t, c = [int(x) for x in input().split(' ')]
        adj[f].insert(0, (t, c))
        adj[t].insert(0, (f, c))

    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    solve(N, K, adj, queries)



if __name__ == '__main__':
    main()
    


Fixed submission:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


# データの入力
N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])

# 経路の探索
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  # 各ノードの訪問状態
d = [float('inf')] * (N+1)  # 始点からの重み

# dijkstra
d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY

# 結果の表示
for x, y in queries:
    print(d[x] + d[y])

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


def solve(N, K, data):
    WHITE, GRAY, BLACK = 0, 1, 2

    num_of_nodes = N+1
    color = [WHITE] * num_of_nodes  # 各ノードの訪問状態
    d = [float('inf')] * num_of_nodes  # 始点からの重み
    adj = [[] for _ in range(num_of_nodes)]

    for f, t, c in data:
        adj[f].insert(0, (t, c))
        adj[t].insert(0, (f, c))


    # dijkstra(self, start):
    d[K] = 0
    pq = [(0, K)]

    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue

        for v, c in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d



def main():
    # データの入力
    N = int(input())
    data = []
    for i in range(N-1):
        data.append(list(map(int, input().split(' '))))
    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    d = solve(N, K, data)

    # 結果の表示
    for q in queries:
        print(d[q[0]] + d[q[1]])


if __name__ == '__main__':
    main()
    


Fixed submission:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


# データの入力
N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])

# 経路の探索
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  # 各ノードの訪問状態
d = [float('inf')] * (N+1)  # 始点からの重み

# dijkstra
d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY

# 結果の表示
for x, y in queries:
    print(d[x] + d[y])

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ

from enum import Enum
from heapq import heappush, heappop


class Sssp(object):
    """ single source shortest path """
    class Status(Enum):
        """ ノードの訪問状態 """
        white = 1  # 未訪問
        gray = 2  # 訪問中
        black = 3  #訪問済

    def __init__(self, N, data):
        num_of_nodes = N+1
        self.color = [Sssp.Status.white] * num_of_nodes  # 各ノードの訪問状態
        self.d = [float('inf')] * num_of_nodes  # 始点からの重み
        self.adj = [[] for _ in range(num_of_nodes)]
        self.make_adj(data)

    def make_adj(self, data):
        # 隣接リストの作成 (接続先 コスト)のタプル
        for f, t, c in data:
            self.adj[f].insert(0, (t, c))
            self.adj[t].insert(0, (f, c))

    def dijkstra(self, start):
        self.d[start] = 0
        pq = [(0, start)]
        #heappush(pq, (0, start))
        remaining = len(self.d) - 1

        while pq and remaining:
            cost, u = heappop(pq)
            self.color[u] = Sssp.Status.black
            remaining -= 1
            if self.d[u] < cost:
                continue

            for v, c in self.adj[u]:
                if self.color[v] == Sssp.Status.black:
                    continue
                if self.d[v] > self.d[u] + c:
                    self.d[v] = self.d[u] + c
                    heappush(pq, (self.d[v], v))
                    self.color[v] = Sssp.Status.gray


def main():
    # データの入力
    N = int(input())
    data = []
    for i in range(N-1):
        data.append(list(map(int, input().split(' '))))
    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    s = Sssp(N, data)
    s.dijkstra(K)

    # 結果の表示
    for q in queries:
        print(s.d[q[0]] + s.d[q[1]])



if __name__ == '__main__':
    main()
    


Fixed submission:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


# データの入力
N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])

# 経路の探索
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  # 各ノードの訪問状態
d = [float('inf')] * (N+1)  # 始点からの重み

# dijkstra
d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY

# 結果の表示
for x, y in queries:
    print(d[x] + d[y])

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった

from enum import Enum
from heapq import heappush, heappop
import numpy as np


class Sssp(object):
    """ single source shortest path """
    class Status(Enum):
        """ ノードの訪問状態 """
        white = 1  # 未訪問
        gray = 2  # 訪問中
        black = 3  #訪問済

    def __init__(self, N, data):
        num_of_nodes = N+1
        self.color = [Sssp.Status.white] * num_of_nodes  # 各ノードの訪問状態
        # self.d = [float('inf')] * num_of_nodes  # 始点からの重み
        self.d = np.array([float('inf')] * num_of_nodes)
        self.adj = [[] for _ in range(num_of_nodes)]
        self.make_adj(data)

    def make_adj(self, data):
        # 隣接リストの作成 (接続先 コスト)のタプル
        for f, t, c in data:
            self.adj[f].insert(0, (t, c))
            self.adj[t].insert(0, (f, c))

    def dijkstra(self, start):
        self.d[start] = 0
        pq = [(0, start)]
        #heappush(pq, (0, start))

        while pq:
            cost, u = heappop(pq)
            self.color[u] = Sssp.Status.black
            if self.d[u] < cost:
                continue

            for v, c in self.adj[u]:
                if self.color[v] == Sssp.Status.black:
                    continue
                if self.d[v] > self.d[u] + c:
                    self.d[v] = self.d[u] + c
                    heappush(pq, (self.d[v], v))
                    self.color[v] = Sssp.Status.gray


def main():
    # データの入力
    N = int(input())
    data = []
    for i in range(N-1):
        data.append(list(map(int, input().split(' '))))
    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    s = Sssp(N, data)
    s.dijkstra(K)

    # 結果の表示
    for q in queries:
        print(int(s.d[q[0]] + s.d[q[1]]))



if __name__ == '__main__':
    main()
    


Fixed submission:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


# データの入力
N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])

# 経路の探索
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  # 各ノードの訪問状態
d = [float('inf')] * (N+1)  # 始点からの重み

# dijkstra
d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY

# 結果の表示
for x, y in queries:
    print(d[x] + d[y])

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。

from enum import Enum
from heapq import heappush, heappop


class Sssp(object):
    """ single source shortest path """
    class Status(Enum):
        """ ノードの訪問状態 """
        white = 1  # 未訪問
        gray = 2  # 訪問中
        black = 3  #訪問済

    def __init__(self, N, data):
        num_of_nodes = N+1
        self.color = [Sssp.Status.white] * num_of_nodes  # 各ノードの訪問状態
        self.d = [float('inf')] * num_of_nodes  # 始点からの重み
        self.adj = [[] for _ in range(num_of_nodes)]
        self.make_adj(data)

    def make_adj(self, data):
        # 隣接リストの作成 (接続先 コスト)のタプル
        for f, t, c in data:
            self.adj[f].insert(0, (t, c))
            self.adj[t].insert(0, (f, c))

    def dijkstra(self, start):
        self.d[start] = 0
        pq = [(0, start)]
        #heappush(pq, (0, start))

        while pq:
            cost, u = heappop(pq)
            self.color[u] = Sssp.Status.black
            if self.d[u] < cost:
                continue

            for v, c in self.adj[u]:
                if self.color[v] == Sssp.Status.black:
                    continue
                if self.d[v] > self.d[u] + c:
                    self.d[v] = self.d[u] + c
                    heappush(pq, (self.d[v], v))
                    self.color[v] = Sssp.Status.gray


def main():
    # データの入力
    N = int(input())
    data = []
    for i in range(N-1):
        data.append(list(map(int, input().split(' '))))
    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    s = Sssp(N, data)
    s.dijkstra(K)

    # 結果の表示
    for q in queries:
        print(s.d[q[0]] + s.d[q[1]])



if __name__ == '__main__':
    main()
    


Fixed submission:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


# データの入力
N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])

# 経路の探索
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  # 各ノードの訪問状態
d = [float('inf')] * (N+1)  # 始点からの重み

# dijkstra
d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY

# 結果の表示
for x, y in queries:
    print(d[x] + d[y])

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""


from enum import Enum


class Sssp(object):
    """ single source shortest path """
    INFINITY = 999999999999
    class Status(Enum):
        """ ノードの訪問状態 """
        white = 1  # 未訪問
        gray = 2  # 訪問中
        black = 3  #訪問済

    def __init__(self, N, data):
        num_of_nodes = N+1
        self.color = [Sssp.Status.white] * num_of_nodes  # 各ノードの訪問状態
        self.M = [[Sssp.INFINITY] * num_of_nodes for _ in range(num_of_nodes)]
        self._make_matrix(data)  # dataから作成した隣接行列(未接続部分はコスト無限大に変換済)
        self.d = [Sssp.INFINITY] * num_of_nodes  # 始点からの重み
        self.p = [-1] * num_of_nodes  # 各頂点の親の番号を記録するための配列

    def _make_matrix(self, data):
        """ 重み付き有効グラフの隣接行列を作成する
        入力データは先頭2つが自ノード番号と出次数、以降は出次数の分だけ(接続先ID, 重み)のペアが続く
        """
        for my_id, to_id, cost in data:
            self.M[my_id][to_id] = cost
            self.M[to_id][my_id] = cost


    def dijkstra(self, start):
        self.d[start] = 0
        self.p[start] = -1

        while True:
            mincost = Sssp.INFINITY
            # 以降の処理で親ノードとして働くノードuを選択する
            for i in range(len(self.d)):
                if self.color[i] != Sssp.Status.black and self.d[i] < mincost:  # Sに属しておらず、Sと接続があるノードのうち重みが最小のものを選択
                    mincost = self.d[i]
                    u = i  # uが親ノードのID

            if mincost == Sssp.INFINITY:
                break

            self.color[u] = Sssp.Status.black  # ノードuはSに属している側に

            for v in range(len(self.d)):
                if self.color[v] != Sssp.Status.black and self.M[u][v] != Sssp.INFINITY:
                    # vへの重みを考えた時、新たにSに加わったuからの経路の方が重みが低ければ、その情報で更新する
                    if self.d[u] + self.M[u][v] < self.d[v]:
                        self.d[v] = self.d[u] + self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Sssp.Status.gray


def main():
    # データの入力
    N = int(input())
    data = []
    for i in range(N-1):
        data.append(list(map(int, input().split(' '))))
    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    s = Sssp(N, data)
    s.dijkstra(K)

    # 結果の表示
    for q in queries:
        print(s.d[q[0]] + s.d[q[1]])



if __name__ == '__main__':
    main()
    


Fixed submission:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


# データの入力
N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])

# 経路の探索
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  # 各ノードの訪問状態
d = [float('inf')] * (N+1)  # 始点からの重み

# dijkstra
d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY

# 結果の表示
for x, y in queries:
    print(d[x] + d[y])