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

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    # (i, j)成分はiからjへの直接経路のコスト
    N = int(input())
    graph = [[0] * N for i in range(N)]
    for i in range(N - 1):
        a, b, c = map(int, input().split())
        graph[a - 1][b - 1] = c

    graph = csr_matrix(graph)
    Q, K = map(int, input().split())
    dist_matrix = dijkstra(csgraph=graph, directed=False, indices=K-1, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト

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


resolve()

Fixed submission:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    # (i, j)成分はiからjへの直接経路のコスト
    N=int(input())
    graph = [[0]*N for i in range(N)]
    for i in range(N-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c


    graph = csr_matrix(graph)

    dist_matrix = dijkstra(csgraph=graph, directed=False, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト
    Q,K=map(int,input().split())
    for i in range(Q):
        x,y=map(int,input().split())
        print(int(dist_matrix[x-1][K-1]+dist_matrix[K-1][y-1]))


resolve()

Fixed submission:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    # (i, j)成分はiからjへの直接経路のコスト
    N=int(input())
    graph = [[0]*N for i in range(N)]
    for i in range(N-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c


    graph = csr_matrix(graph)

    dist_matrix = dijkstra(csgraph=graph, directed=False, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト
    Q,K=map(int,input().split())
    for i in range(Q):
        x,y=map(int,input().split())
        print(int(dist_matrix[x-1][K-1]+dist_matrix[K-1][y-1]))


resolve()

Fixed submission:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall

    # (i, j)成分はiからjへの直接経路のコスト
    N=int(input())
    graph = [[0]*N for i in range(N)]
    for i in range(N-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c


    graph = csr_matrix(graph)

    dist_matrix = floyd_warshall(csgraph=graph, directed=False, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト
    Q,K=map(int,input().split())
    for i in range(Q):
        x,y=map(int,input().split())
        print(int(dist_matrix[x-1][K-1]+dist_matrix[K-1][y-1]))


resolve()

Fixed submission:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall

    # (i, j)成分はiからjへの直接経路のコスト
    N=int(input())
    graph = [[0]*N for i in range(N)]
    for i in range(N-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c


    graph = csr_matrix(graph)

    dist_matrix = floyd_warshall(csgraph=graph, directed=False, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト
    Q,K=map(int,input().split())
    for i in range(Q):
        x,y=map(int,input().split())
        print(int(dist_matrix[x-1][K-1]+dist_matrix[K-1][y-1]))


resolve()

Fixed submission:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N=int(input())
    V, E= N,N-1
    g = [[] for i in range(V)]

    for i in range(E):
        s, t, d = map(int, input().split())
        s,t,d=s-1,t-1,d
        g[s].append((d, t))
        g[t].append((d, s))# g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

    INF = 10 ** 20

    Q,K=map(int,input().split())
    l1=[INF]*V
    l2=[INF]*V
    for i in range(V):
        l1[i]=dijkstra(V, g, i)[K - 1]
        l2[i] = dijkstra(V, g, K-1)[i]

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


resolve()

Fixed submission:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
# import bisect
# from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N=int(input())
    V, E= N,N-1
    g = [[] for i in range(V)]

    for i in range(E):
        s, t, d = map(int, input().split())
        s,t,d=s-1,t-1,d
        g[s].append((d, t))
        g[t].append((d, s))# g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

    INF = 10 ** 20

    Q,K=map(int,input().split())
    for j in range(Q):
        x,y=map(int,input().split())
        print(dijkstra(V,g,x-1)[K-1]+dijkstra(V,g,K-1)[y-1])



resolve()

Fixed submission:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
# import bisect
# from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N=int(input())
    V, E= N,N-1
    g = [[] for i in range(V)]

    for i in range(E):
        s, t, d = map(int, input().split())
        s,t,d=s-1,t-1,d
        g[s].append((d, t))
        g[t].append((d, s))# g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

    INF = 10 ** 20

    Q,K=map(int,input().split())
    for j in range(Q):
        x,y=map(int,input().split())
        print(dijkstra(V,g,x-1)[K-1]+dijkstra(V,g,K-1)[y-1])



resolve()

Fixed submission:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()