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):
N = int(input())
D = {i: [] for i in range(N)}
DD = {}
L = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
dist = [-1 for i in range(N)]
for i in range(N-1):
  D[L[i][0]-1].append(L[i][1]-1)
  D[L[i][1]-1].append(L[i][0]-1)
  DD[(L[i][0]-1)*N+L[i][1]-1], DD[(L[i][1]-1)*N+L[i][0]-1] = L[i][2], L[i][2]
dist[K-1] = 0
p = [K-1]
while p != []:
  n = len(p)
  for i in range(n):
    q = p[i]
    X = D[q][:]
    for j in X:
      if dist[j] < 0:
        dist[j] = dist[q] + DD[q*N+j]
        p.append(j)
  p = p[n:]
for i in range(Q):
  x, y = map(int, input().split())
  print(dist[x-1] + dist[y-1])

Solution (Python):
from heapq import heappush,heapify,heappop
import sys
input = sys.stdin.readline
INF = 10**18

n = int(input())

es=[[] for _ in range(n)] 
d = [INF]*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 dijkstra(s):
    v = -1
    que = [(0,s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que, (d[e[0]], e[0])) 
q,k=map(int,input().split())
dijkstra(k-1)
for i 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())
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):


import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adjs[a - 1].append((b - 1, c))
        adjs[b - 1].append((a - 1, c))
    q, k = map(int, input().split())

    
    dist = [None] * n
    dist[k - 1] = 0
    hq = [(0, k - 1)]
    queued = [False] * n
    queued[k - 1] = True
    while hq:
        d, j = hq.pop()
        dist[j] = d
        for j2, d2 in adjs[j]:
            if queued[j2]:
                continue
            hq.append((d + d2, j2))
            queued[j2] = True

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

if __name__ == "__main__":
    main()

Solution (Python):


import sys
import heapq

def main():
    input = sys.stdin.readline
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adjs[a - 1].append((b - 1, c))
        adjs[b - 1].append((a - 1, c))
    q, k = map(int, input().split())

    
    dist = [None] * n
    dist[k - 1] = 0
    hq = [(0, k - 1)]
    queued = [False] * n
    queued[k - 1] = True
    while hq:
        d, j = heapq.heappop(hq)
        dist[j] = d
        for j2, d2 in adjs[j]:
            if queued[j2]:
                continue
            heapq.heappush(hq, (d + d2, j2))
            queued[j2] = True

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

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
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()
co = dict()
g = [[] for _ in range(n)]
cost = [-1] * n
for i in range(n-1):
    a,b,c = inpl()
    a -= 1; b -= 1
    g[a] += [b]; g[b] += [a]
    co[(a,b)] = c; co[(b,a)] = c
Q,k = inpl()
k -= 1; cost[k] = 0
q = deque()
q.append(k)
while q:
    nv = q.popleft()
    for v in g[nv]:
        if cost[v] > 0:
            continue
        cost[v] = cost[nv] + co[(v,nv)]
        q.append(v)
for _ in range(Q):
    a,b = inpl()
    a -= 1; b -= 1
    print(cost[a] + cost[b])

Solution (Python):
n = int(input())
E = [[] for i in range(n)]
for i in range(n-1):
    ai,bi,ci = map(int, input().split( ))
    ai-=1;bi-=1
    E[ai].append((bi,ci))
    E[bi].append((ai,ci))

from collections import deque
Q = deque()

q,k = map(int, input().split( ))
k-=1
Q.append(k)
d = [-1]*n 
d[k] = 0
while Q:
    v = Q.popleft()
    for u,c in E[v]:
        if d[u]<0:
            d[u] = d[v]+c
            Q.append(u)

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

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

Q,K=map(int,input().split())

par=[-2 for i in range(N)]
par[K-1]=-1
q=deque([K-1])
while q:
    i=q.popleft()
    for j,c in ver[i]:
        if par[j]==-2:
            par[j]=i
            q.append(j)

cost=[-1 for i in range(N)]
cost[K-1]=0
stack=[[K-1,0]]
while stack:
    i,c=stack.pop()
    for j,d in ver[i]:
        if par[i]!=j:
            cost[j]=c+d
            stack.append([j,cost[j]])

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

Solution (Python):
from collections import deque
import heapq
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=[K]
heapq.heapify(stack)
while len(stack)>0:
    n=heapq.heappop(stack)
    for s,t in numbers[n]:
        if visited[s]==inf:
            heapq.heappush(stack,s)
            visited[s]=visited[n]+t
for z in keika:
    print(visited[z[0]]+visited[z[1]])

Solution (Python):
N = int(input())
T = {i: [] for i in range(N)}
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    T[a - 1].append((b - 1, c))
    T[b - 1].append((a - 1, c))

Q, K = map(int, input().split())
S, D = [(-1, K - 1)], [0] * N
while len(S) > 0:
    p, c = S.pop()
    for g, d in T[c]:
        if g != p:
            D[g] = D[c] + d
            S.append((c, g))

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

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

N = int(input())
T, D = {i: [] for i in range(N)}, [-1] * N
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    T[a - 1].append((b - 1, c))
    T[b - 1].append((a - 1, c))


def dfs(p, c, d):
    D[c] = d
    for c2, d2 in T[c]:
        if c2 != p:
            dfs(c, c2, d + d2)


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

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
  e[v].append((u, c))
Q, K = map(int, input().split())
import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
dij = dijkstra(N, e)
p = dij.path(K, 0)

for _ in range(Q):
  u, v = map(int, input().split())
  print(p[u] + p[v])

Solution (Python):
from collections import deque
from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
T = defaultdict(list)
for _ in range(N-1):
    a, b, c = list(map(int, input().split()))
    T[a].append((b, c))
    T[b].append((a, c))

Q, K = list(map(int, input().split()))

distance = [-1] * (N+1)
distance[K] = 0

d = deque()
d.append(K)

while d:
    node = d.popleft()
    for bc in T[node]:
        b, c = bc
        if distance[b] == -1:
            distance[b] = distance[node] + c
            d.append(b)

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

Solution (Python):
from collections import deque
import sys
input = sys.stdin.buffer.readline

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
XY = [tuple(map(int, input().split())) for _ in range(Q)]

que = deque([(K, -1, 0)])
dist = [10**18] * N
while que:
    now, pr, d = que.popleft()
    dist[now] = d
    for to, c in edges[now]:
        if to == pr:
            continue
        que.append((to, now, d + c))

ans = [dist[x - 1] + dist[y - 1] for x, y in XY]
print(*ans, sep='\n')

Solution (Python):
from sys import stdin
from collections import deque
def main():
    readline=stdin.readline
    N=int(readline())
    G=[[] for _ in range(N)]
    a=[0]*(N-1)
    b=[0]*(N-1)
    c=[0]*(N-1)
    for i in range(N-1):
        a[i],b[i],c[i]=map(int,readline().split())
        a[i]-=1
        b[i]-=1
        G[a[i]].append([b[i],c[i]])
        G[b[i]].append([a[i],c[i]])
    Q,K=map(int,readline().split())
    K-=1
    x=[0]*Q
    y=[0]*Q
    for i in range(Q):
        x[i],y[i]=map(int,readline().split())
        x[i]-=1
        y[i]-=1

    que=deque([[K,0]])
    l=[0]*N
    is_searched=[False]*N
    is_searched[K]=True
    while len(que)>=1:
        now=que.popleft()
        l[now[0]]=now[1]
        for nex in G[now[0]]:
            if is_searched[nex[0]]==False:
                is_searched[nex[0]]=True
                que.append([nex[0],l[now[0]]+nex[1]])

    for i in range(Q):
        print(l[x[i]]+l[y[i]])

if __name__=="__main__":
    main()

Solution (Python):
from heapq import heappop, heappush

def dijkstra(s):
    used = [1] * N
    dp = [INF] * N
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

INF = 10 ** 18
N = int(input())
cost = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    cost[a].append([c, b])
    cost[b].append([c, a])

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

Solution (Python):
from collections import deque
n=int(input())
G=[[] for i in range(n)]
dist=[-1]*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())
k-=1
q=deque()
q.append(k)
dist[k]=0
while q:
    cur=q.popleft()
    for nx,nx_d in G[cur]:
        if dist[nx]!=-1:continue
        dist[nx]=dist[cur]+nx_d
        q.append(nx)

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

Solution (Python):





from heapq import heappush, heappop
INF = 10**30
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = [int(i)-1 for i in input().split()]
    c += 1
    G[a].append((b, c))
    G[b].append((a, c))

Q, K = [int(i) for i in input().split()]
K -= 1

d = dijkstra(N, G, K)

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

Solution (Python):
def main():
    from heapq import heappop, heappush
    import sys
    input = sys.stdin.buffer.readline
    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))
    Q, K = (int(i) for i in input().split())

    def dijkstra(s, G):
        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

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


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = map(int, input().split())
dist = dijkstra(G, N+1, K)
for _ in range(Q):
    x, y = map(int, input().split())
    print(dist[x] + dist[y])

Solution (Python):
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
n=int(input())
edge=[[]for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  a-=1;b-=1
  edge[a].append([b,c])
  edge[b].append([a,c])
q,k=map(int,input().split())
k-=1
xy=[list(map(int,input().split()))for _ in range(q)]
for i in range(q):xy[i][0]-=1;xy[i][1]-=1
edge=dijkstra(k,n,edge)
for x,y in xy:print(edge[x]+edge[y])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**9+1
n = int(input())
graph = [[] for _ in range(n+1)]

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

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


def dfs(v1, parent, add):
    dist[v1] = add
    for v2, d in graph[v1]:
        if v2 == parent:
            continue
        dfs(v2, v1, add + d)

dfs(k, -1, 0)

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

Solution (Python):
from collections import deque

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

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

Que=deque([[k-1,0]])

while Que:
    b,c=Que.popleft()
    distance[b]=c
    for pb,pc in X[b]:
        if distance[pb]==-1:
            Que.append([pb,c+pc])

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

Solution (Python):
from collections import deque

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

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

Que=deque([[k-1,0]])

while Que:
    b,c=Que.popleft()
    if visited[b]==1:
        continue
    visited[b]=1
    distance[b]=c
    for pb,pc in X[b]:
        Que.append([pb,c+pc])

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

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

n = ni()
abc = nan(n - 1)
q, k = na()
k -= 1
xy = nan(q)
tree = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = abc[i]
    a -= 1
    b -= 1
    tree[a].append((b, c))
    tree[b].append((a, c))

def bfs():
    q = deque()
    q.append(k)
    dist = [-1] * n
    dist[k] = 0
    while len(q):
        p = q.popleft()
        for i, w in tree[p]:
            if dist[i] != -1:
                continue
            dist[i] = dist[p] + w
            q.append(i)
    return dist

dist = bfs()
for i in range(q):
    x, y = xy[i]
    x -= 1
    y -= 1
    print(dist[x] + dist[y])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N = int(input())
T = [[]for i in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    T[a].append((b,c))
    T[b].append((a,c))
Q,K = map(int,input().split())
D = [0]*(N+1)
def f(v,p,cost):
    global T,K,D
    for C in T[v]:
        if C[0]!=p:
            D[C[0]] = cost+C[1]
            f(C[0],v,cost+C[1])
f(K,0,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(D[x]+D[y])

Solution (Python):
from collections import defaultdict
n = int(input())
tree = dict()
graph = defaultdict(list)

for i in range(n-1):
    a,b,c = (int(x) for x in input().split())
    tree[a,b] = c
    tree[b,a] = c
    graph[a].append(b)
    graph[b].append(a)

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

dist = dict()
stack = [k,]
visited = [False for _ in range(n+1)]
dist[k] = 0
visited[k] = True

while stack:
    new_stack = []
    for node in stack:
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node]  = True
                dist[next_node] = dist[node] + tree[node, next_node]
                new_stack.append(next_node)
    stack = new_stack

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

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


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



edge = [[] for _ in range(N+1)]

for _ in range(N-1):
  A, B, C = map(int, input().split())
  edge[A].append((C,B))
  edge[B].append((C,A))

Q,K = map(int, input().split())

d = dijkstra_heap(K,edge)

ans = []
for q in range(Q):
  x,y = map(int, input().split())
  ans.append(d[x]+d[y])


print(*ans, sep='\n')

Solution (Python):
import heapq
import sys

N = int(input())
d = [[] for i in range(N)]
for i in range(N - 1):
	a, b, c = map(int, input().split())
	d[a - 1].append([b - 1, c])
	d[b - 1].append([a - 1, c])
Q, K = map(int, input().split())
e = [[0, K - 1]]
f = [False] * N
g = [sys.maxsize] * N
g[K - 1] = 0
while len(e):
	h = heapq.heappop(e)
	f[h[1]] = True
	for i in d[h[1]]:
		if not f[i[0]]:
			if g[h[1]] + i[1] < g[i[0]]:
				g[i[0]] = g[h[1]] + i[1]
				heapq.heappush(e, [g[i[0]], i[0]])
for i in range(Q):
	x, y = map(int, input().split())
	print(g[x - 1] + g[y - 1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def dfs_rec(start,prev,c):
    cost[start] = cost[prev] + c
    for node,c in tr[start]:
        if node!=prev:
            dfs_rec(node,start,c)
    return


n  = int(input())
tr = [[] for i in range(n)]
cost = [0]*n
for i in range(n-1):
    a,b,c = map(int,input().split())
    tr[a-1].append([b-1,c])
    tr[b-1].append([a-1,c])

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

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
input=lambda :sys.stdin.readline().rstrip()

N=int(input())
ABC=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(Q)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])
    data[b].append([a,c])

visited=set()
stack=deque([[K,0]])
lst=[0 for i in range(N+1)]
while stack:
    a,m=stack.popleft()
    lst[a]=m
    for p,c in data[a]:
        if not p in visited:
            visited.add(p)
            stack.append([p,m+c])

for x,y in XY:
    print(lst[x]+lst[y])

Solution (Python):

from heapq import heappop, heappush
import sys
sys.setrecursionlimit(100000)
inf = 10 ** 15

def dijkstra(s):
    que = []
    d[s] = 0
    heappush(que, (0,s))
    
    while len(que):
        dist, node = heappop(que)
        
        if d[node] < dist:
            continue
        for to, cost in edges[node]:
            if d[to] > dist + cost:
                d[to] = dist + cost
                heappush(que, (d[to], to))
                
n = int(input())
edges = [[] for _ in range(n)]
for _ 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())
d = [inf for _ in range(n)]
dijkstra(k-1)

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

Solution (Python):
from collections import deque
n=int(input())
G=[[] for i in range(n)]
dist=[-1]*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())
k-=1

dist[k]=0
q=deque()
q.append(k)
while q:
    cur=q.popleft()
    for nx,nx_dist in G[cur]:
        if dist[nx]==-1:
            dist[nx]=dist[cur]+nx_dist
            q.append(nx)

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

Solution (Python):
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
import sys
input = sys.stdin.readline
n =int(input())
 
edge = [[] for i 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 = k-1
d = dijkstra_heap(k)
for i in range(q):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  print(d[x]+d[y])

Solution (Python):
from collections import deque
def main():
    n = int(input())
    tree = [[] for _ in range(n+1)]

    for i in range(n-1):
        a, b, c = map(int, input().split())
        tree[a].append([b, c])
        tree[b].append([a, c])
    q, k = map(int, input().split())
    que = deque([k])
    visit = [-1 for _ in range(n+1)]
    visit[k] = 0
    while que:
        pos = que.popleft()
        for i, j in tree[pos]:
            if visit[i] < 0:
                visit[i] = visit[pos]+j
                que.append(i)
    for i in range(q):
        x, y = map(int, input().split())
        print(visit[x]+visit[y])

if __name__=="__main__":
    main()

Solution (Python):
def main():
    n = int(input())
    tree = [[] for _ in range(n+1)]

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

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

    from collections import deque
    que = deque([k])
    visit = [-1 for _ in range(n+1)]
    visit[k] = 0
    while que:
        pos = que.popleft()
        for i, j in tree[pos]:
            if visit[i] < 0:
                visit[i] = visit[pos]+j
                que.append(i)
    for i in range(q):
        x, y = map(int, input().split())
        print(visit[x]+visit[y])

if __name__=="__main__":
    main()

Solution (Python):
n = int(input())
tree = [[] for _ in range(n+1)]

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

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

from collections import deque
que = deque([k])
visit = [-1 for _ in range(n+1)]
visit[k] = 0
while que:
    pos = que.popleft()
    for i, j in tree[pos]:
        if visit[i] < 0:
            visit[i] = visit[pos]+j
            que.append(i)
for i in range(q):
    x, y = map(int, input().split())
    print(visit[x]+visit[y])

Solution (Python):
import sys
rline = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(rline())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, rline().split())
    a -= 1
    b -= 1
    graph[a].append([b, c])
    graph[b].append([a, c])
to_k = [0] * N


def dfs(node, parent, dist):
    to_k[node] = dist
    
    for child, d in graph[node]:
        if child != parent:
            dfs(child, node, dist + d)


def solve():
    Q, K = map(int, rline().split())
    K -= 1
    dfs(K, -1, 0)
    for _ in range(Q):
        x, y = map(lambda z: int(z) - 1, rline().split())
        print(to_k[x] + to_k[y])


if __name__ == '__main__':
    solve()

Solution (Python):
N=int(input())
G=[[] for _ in range(N)]
for i in range(N-1):
  x,y,d=map(int,input().split())
  x-=1
  y-=1
  G[x].append((y,d))
  G[y].append((x,d))
Q,K=map(int,input().split())
stack=[K-1]
unseen=[1]*N
dist=[float('inf')]*N
dist[K-1]=0
while stack:
  u=stack.pop()
  unseen[u]=0
  for v,d in G[u]:
    if unseen[v]:
      dist[v]=min(dist[v],dist[u]+d)
      stack.append(v)
for q in range(Q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
def dfs(cur,par,d):
    dist[cur]=d
    for nx,nx_dist in G[cur]:
        if nx==par:continue
        dfs(nx,cur,d+nx_dist)

n=int(input())
G=[[] for i in range(n)]
dist=[0]*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())
k-=1
dfs(k,-1,0)
for i in range(q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(dist[x]+dist[y])

Solution (Python):
import sys
sys.setrecursionlimit(10**5 + 5)

N = int(input())

g = {i: [] for i in range(1, N+1)}

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

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

d = [-1 for _ in range(N+1)]


def dfs(s: int):
    for v, c in g[s]:
        if d[v] == -1:
            d[v] = d[s] + c
            dfs(v)


d[K] = 0
dfs(K)

for x, y in xy:
    print(d[x]+d[y])

Solution (Python):
import heapq as h
import sys

input=sys.stdin.readline

N=int(input())
a=[0 for i in range(0,N-1)]
b=[0 for i in range(0,N-1)]
c=[0 for i in range(0,N-1)]
for i in range(0,N-1):
    a[i],b[i],c[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1

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

distance=[-1 for i in range(0,N)]
Q,K=map(int,input().split())
distance[K-1]=0

q=[]
q.append(K-1)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if distance[p[0]]==-1:
                h.heappush(sub,p[0])
            else:
                distance[x]=distance[p[0]]+p[1]
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

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

for i in range(0,Q):
    print(ans[i])

Solution (Python):
import sys
sys.setrecursionlimit(100005)

N = int(input())

edges = {n: [] for n in range(N+1)}

for _ in range(N-1):
    a, b, c = map(int, input().split())

    edges[a].append((b, c))
    edges[b].append((a, c))

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


d = [-1] * (N+1)
d[K] = 0


def dfs(n: int):
    for m, c in edges[n]:
        if d[m] == -1:
            d[m] = d[n] + c
            dfs(m)


dfs(K)

for x, y in xy:
    print(d[x] + d[y])