Problem:
 Score : 400 points    Problem Statement You are given a tree with N vertices. Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices. The i -th edge (1≤i≤N-1) connects Vertices a_i and b_i , and has a length of c_i .  You are also given Q queries and an integer K . In the j -th query (1≤j≤Q) :   find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K .       Constraints  3≤N≤10^5   1≤a_i,b_i≤N (1≤i≤N-1)   1≤c_i≤10^9 (1≤i≤N-1)   The given graph is a tree.  1≤Q≤10^5   1≤K≤N   1≤x_j,y_j≤N (1≤j≤Q)   x_j≠y_j (1≤j≤Q)   x_j≠K,y_j≠K (1≤j≤Q)          Input Input is given from Standard Input in the following format:  N  a_1  b_1  c_1  :  a_{N-1}  b_{N-1}  c_{N-1}  Q  K  x_1  y_1  :  x_{Q}  y_{Q}       Output Print the responses to the queries in Q lines. In the j -th line j(1≤j≤Q) , print the response to the j -th query.        Sample Input 1 5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5      Sample Output 1 3
2
4  The shortest paths for the three queries are as follows:   Query 1 : Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3   Query 2 : Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2   Query 3 : Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4         Sample Input 2 7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7      Sample Output 2 5
14
22  The path for each query must pass Vertex K=2 .       Sample Input 3 10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10      Sample Output 3 17000000000

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    N = int(input())
    inf = 10**17

    def dijkstra_heap(start,edge):
        
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        
        for a,b in edge[start]:
            heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            
            minedge = heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    
    edge = [[] for i in range(N)]
    
    for _ in range(N-1):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    q,k = map(int, input().split())
    d = dijkstra_heap(k-1, edge)

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    N = int(input())
    
    def dfs(v):
        visited[v] = 1
        for cost, nv in edge[v]:
            if visited[nv] == 1:
                continue
            d[nv] = d[v] + cost
            dfs(nv)

    
    edge = [[] for i in range(N)]
    
    for _ in range(N-1):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    q,k = map(int, input().split())
    d = [-1]*N
    d[k-1] = 0
    visited = [0]*N
    dfs(k-1)

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    N = int(input())
    
    def dfs(v):
        visited[v] = 1
        for cost, nv in edge[v]:
            if visited[nv] == 1:
                continue
            d[nv] = d[v] + cost
            dfs(nv)

    
    edge = [[] for i in range(N)]
    
    for _ in range(N-1):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    q,k = map(int, input().split())
    d = [-1]*N
    d[k-1] = 0
    visited = [0]*N
    dfs(k-1)

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    N = int(input())
    inf = 10**17

    def dijkstra_heap(start,edge):
        
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        
        for a,b in edge[start]:
            heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            
            minedge = heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    
    edge = [[] for i in range(N)]
    
    for _ in range(N-1):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    q,k = map(int, input().split())
    d = dijkstra_heap(k-1, edge)

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

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

N = int(input())
edges = {i: [] for i in range(N)}
for i in range(N - 1):
    a, b, c = map(int, input().split(" "))
    edges[a - 1].append((b - 1, c))
    edges[b - 1].append((a - 1, c))
Q, K = map(int, input().split(" "))


dist = [-1 for i in range(N)]
que = []
heapq.heappush(que, (0, K - 1, -1)) 
while len(que) > 0:
    d, ind, par = heapq.heappop(que)
    if dist[ind] != -1:
        continue
    dist[ind] = d
    for edge in edges[ind]:
        if edge[0] == par:
            continue
        heapq.heappush(que, (d + edge[1], edge[0], ind))

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

Solution (Python):
import heapq

N = int(input())
edges = {i: [] for i in range(N)}
for i in range(N - 1):
    a, b, c = map(int, input().split(" "))
    edges[a - 1].append((b - 1, c))
    edges[b - 1].append((a - 1, c))
Q, K = map(int, input().split(" "))


dist = [-1 for i in range(N)]
que = []
heapq.heappush(que, (0, K - 1, -1)) 
while len(que) > 0:
    d, ind, par = heapq.heappop(que)
    if dist[ind] != -1:
        continue
    dist[ind] = d
    for edge in edges[ind]:
        if edge[0] == par:
            continue
        heapq.heappush(que, (d + edge[1], edge[0], ind))

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import heapq


def dijkstra_heap(s, edge):
    
    d = [10 ** 20] * n
    used = [True] * n  
    d[s] = 0
    used[s] = False
    edgelist = []
    for a, b in edge[s]:
        heapq.heappush(edgelist, a * (10 ** 6) + b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge % (10 ** 6)]:
            continue
        v = minedge % (10 ** 6)
        d[v] = minedge // (10 ** 6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, (e[0] + d[v]) * (10 ** 6) + e[1])
    return d


n = int(readline())
edge = [[] for i in range(n)]
for i in range(n - 1):
    a, b, c = map(int, readline().split())
    edge[a - 1].append([c, b - 1])
    edge[b - 1].append([c, a - 1])
q, k = map(int, readline().split())
check = dijkstra_heap(k - 1, edge)
for i in range(q):
    x, y = map(int, readline().split())
    print(check[x - 1] + check[y - 1])

Solution (Python):
import heapq
N = int(input())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    ta,tb,tc = map(int, input().split())
    E[ta].append([tc,tb])
    E[tb].append([tc,ta])

Q, K = map(int, input().split())
inf = float('inf')
D = [inf] * (N+1)

q = []
heapq.heappush(q,[0,K])
cnt = 0
while True:
    d, cp = heapq.heappop(q)
    if D[cp] != inf:
        continue
    else:
        D[cp] = d
        cnt += 1
        if cnt == N:
            break

        for nd,np in E[cp]:
            heapq.heappush(q,[D[cp]+nd, np])

ans = []
for _ in range(Q):
    ts,tg = map(int, input().split())
    ans.append(D[ts]+D[tg])

for a in ans:
    print(a)

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    N = iip(False)
    edge = {}
    for i in range(N):
        edge[i] = []

    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        edge[a].append((b, c))
        edge[b].append((a, c))

    Q, K = iip()

    q = []
    for i in range(Q):
        q.append(iip())

    que = deque()
    que.append(K-1)
    distanse = [False for i in range(N)]
    distanse[K-1] = 0
    while que:
        node = que.popleft()
        dis = distanse[node]

        for next, c in edge[node]:
            if distanse[next] is not False:
                continue
            distanse[next] = dis + c
            que.append(next)

    

    ans = []
    for i, j in q:
        ans.append(distanse[i-1]+distanse[j-1])

    split_print_enter(ans)






def iip(listed=True, num_only=True):  
    if num_only:
        ret = [int(i) for i in input().split()]
    else:
        ret = [int(i) if i in _NUMINT_ALL else i for i in input().split()]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def iipt(l, listed=False, num_only=True):  
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed, num_only=num_only))
    return ret


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
def main():
    n = int(input())
    a = []
    b = []
    c = []
    lst = [[] for _ in range(n)]

    for i in range(n - 1):
        aa, bb, cc = map(int,input().split())
        lst[aa - 1].append((bb - 1, cc))
        lst[bb - 1].append((aa - 1, cc))

    q, k = map(int,input().split())
    x = []
    y = []
    for i in range(q):
        xx, yy = map(int,input().split())
        x.append(xx - 1)
        y.append(yy - 1)
    qq = deque()
    qq.append(k - 1)
    dist = [0] * n
    while len(qq) != 0:
        now = qq.popleft()
        for to, w in lst[now]:
            if dist[to] != 0:
                continue
            dist[to] = dist[now] + w
            qq.append(to)

    for i in range(q):
        print(dist[x[i]] + dist[y[i]])





if __name__ == '__main__':
    main()

Solution (Python):
import queue
def main():
    n = int(input())
    a = []
    b = []
    c = []
    lst = [[] for _ in range(n)]

    for i in range(n - 1):
        aa, bb, cc = map(int,input().split())
        lst[aa - 1].append((bb - 1, cc))
        lst[bb - 1].append((aa - 1, cc))

    q, k = map(int,input().split())
    x = []
    y = []
    for i in range(q):
        xx, yy = map(int,input().split())
        x.append(xx - 1)
        y.append(yy - 1)
    qq = queue.Queue()
    qq.put(k - 1)
    dist = [0] * n
    while not qq.empty():
        now = qq.get()
        for to, w in lst[now]:
            if dist[to] != 0:
                continue
            dist[to] = dist[now] + w
            qq.put(to)

    for i in range(q):
        print(dist[x[i]] + dist[y[i]])





if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
adj = [[] for _ in range(n)]  

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

q, k = map(int, input().split())
k -= 1
dist = [-1]*n  
dist[k] = 0  

stack = [k]  

while stack: 
    now = stack.pop()
    for dest, cost in adj[now]:
        if dist[dest] != -1: 
            continue
        dist[dest] = dist[now] + cost 
        stack.append(dest)

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

Solution (Python):
n = int(input())
adj = [[] for _ in range(n)]  

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

q, k = map(int, input().split())
k -= 1
dist = [-1]*n  
dist[k] = 0  

stack = [k]  

while stack: 
    now = stack.pop()
    for dest, cost in adj[now]:
        if dist[dest] != -1: 
            continue
        dist[dest] = dist[now] + cost 
        stack.append(dest)

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
g = [[] for _ in range(n)]
cost = dict()
for i in range(n-1):
    a,b,c = inpl()
    a -= 1; b -= 1
    g[a].append(b); g[b].append(a)
    cost[(a,b)] = c; cost[(b,a)] = c
Q,k = inpl()
k -= 1
q = deque()
q.append(k)
dist = [-1] * n
dist[k] = 0
while q:
    v = q.popleft()
    for nv in g[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + cost[(nv,v)]
        q.append(nv)
for _ in range(Q):
    a,b = inpl()
    print(dist[a-1] + dist[b-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)


N = int(input())
abc=[]
for _ in range(N-1):
    abc.append(tuple(map(int, input().split())))
Q, K = map(int, input().split())
xy=[]
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))



G = [[] for _ in range(N+1)]
for el in abc:
    a,b,c = el
    G[a].append((b,c))
    G[b].append((a,c))


seen=[False]*(N+1)
distance=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for el in G[n]:
        if seen[el[0]] == False:
            distance[el[0]] = distance[n] + el[1]
            dfs(el[0])
dfs(K)


for q in xy:
    print(distance[q[0]]+distance[q[1]])

Solution (Python):
from collections import deque


def main():
    n = int(input())
    tree = [[] for _ in range(n)]
    dist = [0 for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        tree[a - 1].append([b - 1, c])
        tree[b - 1].append([a - 1, c])
    q, k = map(int, input().split())
    k -= 1
    s = deque([k])
    dist[k] = -1
    while s:
        now = s.pop()
        for t, d in tree[now]:
            if dist[t] == 0:
                dist[t] = dist[now] + d
                dist[t] += 1 if now == k else 0
                s.append(t)
    dist[k] = 0
    for _ in range(q):
        x, y = map(lambda x: int(x) - 1, input().split())
        print(dist[x] + dist[y])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    G=[[] for _ in range(N)]
    for _ 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

    dfromK = [-1] * N
    dfromK[K] = 0
    stk = [(K,0)]
    while stk:
        v,d=stk.pop()
        for to,c in G[v]:
            if dfromK[to] >= 0: continue
            dfromK[to] = d+c
            stk.append((to,d+c))

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

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, cost))
    edges[to].append((fr, cost))

Q, K = map(int, input().split())
K -= 1
ST = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(Q)]


minDist = [10**18] * N
st = [(K, 0, -1)]
while st:
    now, d, pr = st.pop()
    minDist[now] = d
    for to, cost in edges[now]:
        if to == pr:
            continue
        st.append((to, d + cost, now))

ans = []
for s, t in ST:
    ans.append(minDist[s] + minDist[t])
print(*ans, sep='\n')

Solution (Python):
from heapq import heappop,heappush
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a,b,c = map(int, input().split())
    G[a-1].append({"to":b-1, "cost":c})
    G[b-1].append({"to":a-1, "cost":c})
Q,K = map(int, input().split())
K -= 1

dist = [float("inf")] * N
dist[K] = 0
que = [(0, K)]

while que:
    d,v = heappop(que)
    if dist[v] < d: continue
    for e in G[v]:
        if dist[e["to"]] > d + e["cost"]:
            dist[e["to"]] = d + e["cost"]
            heappush(que, (dist[e["to"]], e["to"]))

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

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())

import heapq
def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n,w = n, n - 1

edge = [[] for i in range(n)]

for i in range(w):
    x,y,z = map(int,input().split())
    edge[x - 1].append([z,y - 1])
    edge[y - 1].append([z,x - 1]) 

q, k = [int(x) for x in input().split()]

k_dis = dijkstra_heap(k - 1)

for _ in range(q):
    s, g = [int(x) for x in input().split()]
    print(k_dis[s - 1] + k_dis[g - 1])

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    from heapq import heappop, heappush
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c, b-1))
        edge[b-1].append((c, a-1))

    def dijkstra(G, s):
        d = [10**12]*N
        used = [True] * N  
        d[s] = 0
        used[s] = False
        edges = []
        for e in G[s]:
            heappush(edges, e)
        while len(edges):
            c, v = heappop(edges)
            if not used[v]:
                continue
            d[v] = c
            used[v] = False
            for nexc, nexv in G[v]:
                if used[nexv]:
                    heappush(edges, (nexc+c, nexv))
        return d

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


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):
import sys
input = sys.stdin.readline

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

q, k = map(int, input().split())
k -= 1

import heapq
INF = 10**18
def dijkstra_heap(s, edge):
    d = [INF] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

d = dijkstra_heap(k, edge)


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

Solution (Python):
N = int(input())
ABC = [tuple(map(int,input().split())) for i in range(N-1)]
Q,K = map(int,input().split())
K -= 1
XY = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(Q)]
es = [[] for i in range(N)]
for a,b,c in ABC:
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))
INF = float('inf')
dist = [INF] * N
dist[K] = 0
import heapq
hq = [(0,K)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to,d in es[v]:
        if c+d >= dist[to]: continue
        dist[to] = c+d
        heapq.heappush(hq,(c+d,to))
ans = []
for x,y in XY:
    ans.append(dist[x]+dist[y])
print(*ans, sep='\n')

Solution (Python):
import sys
from collections import deque


IN = sys.stdin.readlines()
N = int(IN[0])

edge = [[] for _ in range(N)]
for i in range(1, N):
    a, b, c = map(int, IN[i].split())
    a -= 1; b -= 1
    edge[a].append((b, c))
    edge[b].append((a, c))

Q, K = map(int, IN[N].split())

q = deque()
path = [float('inf')] * N
path[K - 1] = 0
q.append((K - 1, 0))
while q:
    p, step = q.popleft()
    for np, d in edge[p]:
        if path[np] > step + d:
            q.append((np, step + d))
            path[np] = step + d

for i in range(N + 1, N + 1 + Q):
    x, y = map(int, IN[i].split())
    x -= 1; y -= 1
    Kx = path[x]
    Ky = path[y]
    print(Kx + Ky)

Solution (Python):
import heapq
import sys
input=sys.stdin.readline


def dijkstra(s):
    inf=float("inf")
    color=["white" for _ in range(n)]
    D=[inf for _ in range(n)]

    M=[[] for _ in range(n)]
    for a,b,c in ABC:
        M[a-1].append([b-1,c])
        M[b-1].append([a-1,c])

    D[s]=0

    H=[(0,s)]
    heapq.heapify(H)

    while len(H)>=1:
        u=heapq.heappop(H)[1]
        if color[u]=="black":continue
        color[u]="black"

        V=[(i,j) for i,j in M[u] if color[i]!="black"]
        while len(V)!=0:
            for i,j in V:
                if D[u]+j<D[i]:
                    D[i]=D[u]+j
                    color[i]="gray"
                    heapq.heappush(H,(D[i],i))
            break

    return D


n=int(input())
ABC=[list(map(int,input().split())) for _ in range(n-1)]
q,k=map(int,input().split())
XY=[list(map(int,input().split())) for _ in range(q)]
D=dijkstra(k-1)
for x,y in XY:
    print(D[x-1]+D[y-1])

Solution (Python):
import heapq


def dijkstra(s):
    inf=float("inf")
    color=["white" for _ in range(n)]
    D=[inf for _ in range(n)]

    M=[[] for _ in range(n)]
    for a,b,c in ABC:
        M[a-1].append([b-1,c])
        M[b-1].append([a-1,c])

    D[s]=0

    H=[(0,s)]
    heapq.heapify(H)

    while len(H)>=1:
        u=heapq.heappop(H)[1]
        if color[u]=="black":continue
        color[u]="black"

        V=[(i,j) for i,j in M[u] if color[i]!="black"]
        while len(V)!=0:
            for i,j in V:
                if D[u]+j<D[i]:
                    D[i]=D[u]+j
                    color[i]="gray"
                    heapq.heappush(H,(D[i],i))
            break

    return D


n=int(input())
ABC=[list(map(int,input().split())) for _ in range(n-1)]
q,k=map(int,input().split())
XY=[list(map(int,input().split())) for _ in range(q)]
D=dijkstra(k-1)
for x,y in XY:
    print(D[x-1]+D[y-1])

Solution (Python):
n=int(input())
g=[[] for i in range(n)]
for _ in range(n-1):
  u,v,c=map(int,input().split())
  g[u-1].append((v-1,c))
  g[v-1].append((u-1,c))
Q,k=map(int,input().split())
d=[-1]*n
d[k-1]=0
q=[k-1]
while q:
  t=q.pop()
  for x,cost in g[t]:
    if d[x]==-1:
      d[x]=d[t]+cost
      q.append(x)
for _ in range(Q):
  x,y=map(int,input().split())
  print(d[x-1]+d[y-1])

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n= int(input())
bd = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c= map(int,input().split())
    bd[a-1].append((b-1,c))
    bd[b-1].append((a-1,c))
q,k= map(int,input().split())
cost = [0] * n
def dfs(curnode,pre,addcost):
    for abr in bd[curnode]:
        if abr[0]!=pre:
            cost[abr[0]]=addcost+abr[1]
            dfs(abr[0],curnode,addcost+abr[1])
dfs(k-1,-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for _ in range(n)] 
d = [0]*n 
used=[True]*n
for i in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))


def dfs(s,dist):
    used[s]=False
    for v,x in es[s]:
        if used[v]:
            d[v]=dist+x
            dfs(v,dist+x)
q,k=map(int,input().split())
dfs(k-1,0)
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Solution (Python):


from collections import deque


def submit():
    n = int(input())
    edges = {i: [] for i in range(n)}
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append((b, c))
        edges[b].append((a, c))
    
    q, k = map(int, input().split())
    k -= 1
    
    dist = [-1 for _ in range(n)]
    s = deque()
    s.append((k, 0))
    while len(s):
        e, d = s.pop()
        for neignbor, cost in edges[e]:
            if dist[neignbor] < 0:
                dist[neignbor] = d + cost
                s.append((neignbor, d + cost))

    
    res = []
    for _ in range(q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        res.append(dist[x] + dist[y])

    for r in res:
        print(r)


submit()

Solution (Python):
from collections import deque
n = int(input())
d = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append([b,c])
    d[b].append([a,c])
q, k = map(int, input().split())
k -= 1

def bfs():
    d2 = [True] * n
    ans = [0] * n
    que = deque([k])
    d2[k] = False
    while len(que) != 0:
        val = que.popleft()

        for i in range(len(d[val])):
            if d2[d[val][i][0]] == True:
                que.append(d[val][i][0])
                ans[d[val][i][0]] += (ans[val] + d[val][i][1])
                d2[d[val][i][0]] = False
    return ans
ans = bfs()
for i in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(ans[x] + ans[y])

Solution (Python):
from collections import deque
n = int(input())
d = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append([b,c])
    d[b].append([a,c])
q, k = map(int, input().split())
k -= 1

def bfs():
    d2 = [True] * n
    ans = [0] * n
    que = deque([k])
    d2[k] = False
    while len(que) != 0:
        val = que.popleft()

        for i in range(len(d[val])):
            if d2[d[val][i][0]] == True:
                que.append(d[val][i][0])
                ans[d[val][i][0]] += (ans[val] + d[val][i][1])
                d2[d[val][i][0]] = False
    return ans
ans = bfs()
for i in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(ans[x] + ans[y])