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):
from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
tree_dict = defaultdict(set)
cost_dict = dict()
for i in range(N-1):
    a, b, c = tuple(map(int, input().split()))
    tree_dict[a] |= {(b, c)}
    tree_dict[b] |= {(a, c)}
    cost_dict[(a, b)] = c
    cost_dict[(b, a)] = c

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


dist = {K: 0}
q = [(to_node, K) for to_node, cost in tree_dict[K]]
for i in range(N - 1):
    to_node, from_node = q[i]
    dist[to_node] = dist[from_node] + cost_dict[(from_node, to_node)]
    for next_node, cost in tree_dict[to_node]:
        if next_node != from_node:
            q += [(next_node, to_node)]


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

Solution (Python):
from collections import deque

N = int(input())

L = [[] for i in range(N)]

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

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

K -= 1

DISTANCE = [float("inf") for i in range(N)]

DISTANCE[K] = 0

q = deque([K])

while q :
    from_ = q.popleft()
    for to_, weight in L[from_] :
        dist = DISTANCE[from_] + weight
        if dist < DISTANCE[to_] :
            DISTANCE[to_] = dist
            q.append(to_)
            
ans = []

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

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

Solution (Python):
from collections import deque

N = int(input())

L = [[] for i in range(N)]

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

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

K -= 1

DISTANCE = [float("inf") for i in range(N)]

DISTANCE[K] = 0

q = deque([K])

while q :
    from_ = q.popleft()
    for to_, weight in L[from_] :
        dist = DISTANCE[from_] + weight
        if dist < DISTANCE[to_] :
            DISTANCE[to_] = dist
            q.append(to_)
            
ans = []

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

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

Solution (Python):
n = int(input())
g = {}
from collections import deque
for i in range(1,n+1):
    g[i] = deque([])
for _ in range(n-1):
    a,b,c = map(int,input().split())
    g[a].appendleft([b,c])
    g[b].appendleft([a,c])
Q,k = map(int,input().split())
q = [list(map(int,input().split())) for _ in range(Q)]
queue = deque(g[k])
shortest = [0]*(n+1)
while queue:
    a,c = queue.pop()
    shortest[a] = c
    while g[a]:
        v = g[a].pop()
        if shortest[v[0]]==0:
            queue.appendleft([v[0],v[1]+c])
for x,y in q:
    print(shortest[x]+shortest[y])

Solution (Python):
N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = list(map(int, input().split()))
XY = [list(map(int, input().split())) for _ in range(Q)]

adjacent_dict={i:{} for i in range(1,N+1)}
for a,b,c in ABC:
  adjacent_dict[a][b]=c
  adjacent_dict[b][a]=c

from collections import deque
fromK = [0]*(N+1)
stack = deque([K])
while stack:
  k = stack.popleft()
  for v, d in adjacent_dict[k].items():
    if fromK[v] == 0:
      fromK[v] = fromK[k]+d
      stack.append(v)

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

Solution (Python):
import sys
sys.setrecursionlimit 
N = int(input())

sys.setrecursionlimit(10**9+1)

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

memo = [0] * (N+1)


def dfs(cur, prev, dist):
      
      memo[cur] = dist
      
      for next, cost in nodes[cur]:
            
            if next == prev:
                  continue
            
            dfs(next, cur, dist+cost)

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

Solution (Python):
import collections

n=int(input())
arr=[[] for _ in range(n+1)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  arr[u].append([v,w])
  arr[v].append([u,w])
m,p=map(int,input().split())
q=collections.deque([p])
check=[False for _ in range(n+1)]
check[p]=True
d=[0 for _ in range(n+1)]
while 1:
  if len(q)==0:
    break
  tmp=q.popleft()
  for i,j in arr[tmp]:
    if check[i]==False:
      check[i]=True
      d[i]=d[tmp]+j
      q.append(i)
for i in range(m):
  u,v=map(int,input().split())
  print(d[u]+d[v])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

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

dist = [None]*(N+1)

def set_dist(x,d):
  dist[x] = d
  for y,dd in edge[x]:
    if dist[y] is not None:
      continue
    set_dist(y,d+dd)

set_dist(K,0)

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

Solution (Python):
n=int(input())
Edges=[]
for i in range(n-1):
  a,b,c=map(int,input().split())
  Edges.append([a,b,c])
q,k=map(int,input().split())
def BFS(K,edges,N):
  roots=[[] for i in range(n)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*n
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
D=BFS(k-1,Edges,n)
for i in range(q):
  x,y=map(int,input().split())
  print(D[x-1]+D[y-1])

Solution (Python):
import sys
input = sys.stdin.readline
n=int(input())
Edges=[]
for i in range(n-1):
  a,b,c=map(int,input().split())
  Edges.append([a,b,c])
q,k=map(int,input().split())
def BFS(K,edges,N):
  roots=[[] for i in range(n)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*n
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
D=BFS(k-1,Edges,n)
for i in range(q):
  x,y=map(int,input().split())
  print(D[x-1]+D[y-1])

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

ed = [ [ int(it) for it in input().split() ] for i in range(N-1) ]
Q,K = [ int(it) for it in input().split() ]
qu = [ [ int(it)-1 for it in input().split() ] for i in range(Q) ]

K = K-1
down = [ [] for i in range(N) ]
for a,b,c in ed:
  down[a-1].append( (b-1,c) )
  down[b-1].append( (a-1,c) )

dist = [10000000000000000000000]*N
dist[K] = 0

now = [K]
for i in range(100000000000000):
  if ( len(now) == 0 ):
    break
  n = now.pop()
  for d,c in down[n]:
    dist[d] = min( dist[d] , dist[n] + c )
    now.append(d)
  down[n] = []
  
for a,b in qu:
  print ( dist[a]+dist[b] )

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

N = int(input())

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


Q, K = [int(i) for i in input().split()]
dist = [0] * (N + 1)
def dfs(cur, parent, d):
    dist[cur] = d
    for to, cost in E[cur]:
        if to == parent:
            continue
        dfs(to, cur, d + cost)
dfs(K, -1, 0)

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

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

Q, K = map(int, input().split())
XY = []
for _ in range(Q):
    x,y = map(int, input().split())
    XY.append((x,y))
    
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: 
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, K)


questions = XY

for x,y in questions:
    ans = shortest[x] + shortest[y]
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)
n=int(input())
G=[[]for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
q, k = map(int,input().split())
d = [0]*(n+1) 
def f(v,p,u): 
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
f(k,0,0)
for i in range(q):
    x, y = map(int,input().split())
    print(d[x]+d[y])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
q, k = map(int,input().split())
d = [0]*(n+1) 
def f(v,p,u): 
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
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
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()

N = int(input())

rows = []
cols = []
weights = []

for _ in range(N-1):
    
    u, v, a = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, a)
    g.add_edge(v-1, u-1, a)

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



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

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()

N = int(input())

rows = []
cols = []
weights = []

for _ in range(N-1):
    
    u, v, a = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, a)
    g.add_edge(v-1, u-1, a)

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



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

Solution (Python):
from heapq import heappush, heappop


N = int(input())
a, b, c = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N else
    ((), ())
)
Q, K = map(int, input().split())
x, y = (
    zip(*(map(int, input().split()) for _ in range(Q))) if Q else
    ((), ())
)


INF = 10**18

G = [{} for _ in range(N + 1)]
for u, v, w in zip(a, b, c):
    G[u][v] = w
    G[v][u] = w


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, K)


ans = '\n'.join(
    str(dp[i] + dp[j])
    for i, j in zip(x, y)
)


print(ans)

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

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


def distance(x, prev, d):
    dp[x] = d
    for i, j in zip(edge[x][0], edge[x][1]):
        if i == prev:
            continue
        if dp[i] != -1:
            continue
        distance(i, x, d + j)
    return

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

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

for i in range(q):
    print(ans[i])

Solution (Python):
import sys
sys.setrecursionlimit(1145141919)
N=int(input())
d=[-1 for _ in range(N+1)]
e=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b,c=map(int,input().split())
	e[a].append((b, c))
	e[b].append((a, c))
Q,K=map(int,input().split())
def dfs(now, dis):
	d[now] = dis
	for nxt,cos in e[now]:
		if d[nxt] == -1:
			dfs(nxt, dis+cos)
dfs(K, 0)
for _ in range(Q):
	x,y=map(int,input().split())
	print(d[x]+d[y])

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


def main():
    N = int(input())

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

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

    ans = ref_pypy(N, abc, Q, K, xy)
    print(*ans, sep="\n")


def ref_pypy(N, abc, Q, K, xy):
    """https://atcoder.jp/contests/abc070/submissions/5331379"""
    L = [-1 for i in range(N+1)]
    L[K] = 0
    n = [[] for i in range(N+1)]
    for a, b, c in abc:
        n[a].append([b, c])
        n[b].append([a, c])

    def dfs(x):
        for i in n[x]:
            if L[i[0]] == -1:
                L[i[0]] = L[x]+i[1]
                dfs(i[0])

    dfs(K)

    ans = []
    for x, y in xy:
        ans.append(L[x] + L[y])

    return ans


if __name__ == "__main__":
    main()

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


def main():
    N = int(input())

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

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

    ans = ref_pypy(N, abc, Q, K, xy)
    print(*ans, sep="\n")


def ref_pypy(N, abc, Q, K, xy):
    """https://atcoder.jp/contests/abc070/submissions/5331379"""
    L = [-1 for i in range(N+1)]
    L[K] = 0
    n = [[] for i in range(N+1)]
    for a, b, c in abc:
        n[a].append([b, c])
        n[b].append([a, c])

    def dfs(x):
        for i in n[x]:
            if L[i[0]] == -1:
                L[i[0]] = L[x]+i[1]
                dfs(i[0])

    dfs(K)

    ans = []
    for x, y in xy:
        ans.append(L[x] + L[y])

    return ans


if __name__ == "__main__":
    main()

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


def main():
    N = int(input())

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

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

    ans = ref_pypy(N, abc, Q, K, xy)
    print(*ans, sep="\n")


def ref_pypy(N, abc, Q, K, xy):
    """https://atcoder.jp/contests/abc070/submissions/5331379"""
    L = [-1 for i in range(N+1)]
    L[K] = 0
    n = [[] for i in range(N+1)]
    for a, b, c in abc:
        n[a].append([b, c])
        n[b].append([a, c])

    def dfs(x):
        for i in n[x]:
            if L[i[0]] == -1:
                L[i[0]] = L[x]+i[1]
                dfs(i[0])

    dfs(K)

    ans = []
    for x, y in xy:
        ans.append(L[x] + L[y])

    return ans


if __name__ == "__main__":
    main()

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

N=int(input())
n=[[]for i in range(N+1)]

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

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

L[K]=0

def dfs(x):
    for i in n[x]:
        if L[i[0]]==-1:
            L[i[0]]=L[x]+i[1]
            dfs(i[0])
dfs(K)



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

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
N=int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    table[a].append((b,c))
    table[b].append((a,c))
Q,K=map(int,input().split())
query=[[int(i)-1 for i in input().split()] for i in range(Q)]
K=K-1
H=[]
visit=[10**18]*(N)
visit[K]=0
heappush(H,(0,K))
while H:
    co,pt=heappop(H)
    if co>visit[pt]:
        continue
    for x,c in table[pt]:
        if visit[x]>visit[pt]+c:
            visit[x]=visit[pt]+c
            heappush(H,(visit[x],x))
for a,b in query:
    print(visit[a]+visit[b])

Solution (Python):
import heapq

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

connect = [[] for _ in range(N)]
INFTY = 10**15
for a,b,c in abc:
    connect[a-1].append([b-1,c])
    connect[b-1].append([a-1,c])

cost = [[INFTY,False] for _  in range(N)]
cost[K-1][0] = 0
q = [(0,K-1)]
while q:
    _,i = heapq.heappop(q)
    if cost[i][1]:
        continue
    cost[i][1] = True
    ci0 = cost[i][0]
    for j,c in connect[i]:
        if cost[j][1]:
            continue
        tmp_cost = ci0+c
        if tmp_cost < cost[j][0]:
            cost[j][0] = tmp_cost
            heapq.heappush(q,(tmp_cost,j))

for x,y in xy:
    print(cost[x-1][0] + cost[y-1][0])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n = int(input())
li = [[] for i in range(n)]

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

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

def dfs(x):
  for node in li[x]:
    if tdp[node[0]] == -1:
      tdp[node[0]] = tdp[x] + node[1]
      dfs(node[0])

dfs(k-1)
for i in range(q):
  a,b = map(int,input().split())
  print(tdp[a-1]+tdp[b-1])

Solution (Python):
from functools import reduce
from collections import deque
import math

def bfs(i,E,N):
    q = deque()
    q.append(i)
    d = [-1]*N
    d[i] = 0
    while q:
        next_node = q.popleft()
        for e in E[next_node]:
            if d[e[0]] == -1:
                d[e[0]] = d[next_node] + e[1]                
                q.append(e[0])
    return d
def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input())
    a = []
    b = []
    c = []
    for i in range(N-1):
        s1,s2,s3 = list(int(_) for _ in input().split())
        a.append(s1-1)
        b.append(s2-1)
        c.append(s3)
    Q,K = list(int(_) for _ in input().split())
    x = []
    y = []
    for i in range(Q):
        s1,s2 = list(int(_) for _ in input().split())
        x.append(s1-1)
        y.append(s2-1)
    
    e = [[] for i in range(N)]
    for i in range(N-1):
        e[a[i]].append((b[i],c[i]))
        e[b[i]].append((a[i],c[i]))

    d = bfs(K-1,e,N)

    for i in range(Q):        
        print(d[x[i]]+d[y[i]])
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
G = [[] for i in range(N)]
for i 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))
d = [0] * N


def dfs(u, p, k):
    d[u] = k
    for w, c in G[u]:
        if w == p:
            continue
        dfs(w, u, k + c)


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

Solution (Python):

import sys

inf = float('inf')

def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    adj = [[] for i in range(N)]
    for i in range(N-1):
        adj[a[i]].append((b[i], c[i]))
        adj[b[i]].append((a[i], c[i]))

    D = [inf for i in range(N)]
    prev = [None for i in range(N)]
    D[K] = 0
    Queue = [K]
    while len(Queue) > 0:
        u = Queue.pop()
        for v, w in adj[u]:
            if v == prev[u]:
                continue
            prev[v] = u
            D[v] = D[u] + w
            Queue.append(v)
    
    for i in range(Q):
        print(D[x[i]] + D[y[i]])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    c = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))-1
        b[i] = int(next(tokens))-1
        c[i] = int(next(tokens))
    Q = int(next(tokens))  
    K = int(next(tokens))-1  
    x = [int()] * (Q)  
    y = [int()] * (Q)  
    for i in range(Q):
        x[i] = int(next(tokens))-1
        y[i] = int(next(tokens))-1
    solve(N, a, b, c, Q, K, x, y)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
edge = [{} for _ in range(N+1)]
dist = [-1]*(N+1)
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a][b] = c
    edge[b][a] = c
Q,K = map(int,input().split())
dist[K] = 0
dfs_stack = [K]
while dfs_stack:
    s = dfs_stack.pop()
    for t,t_dist in edge[s].items():
        if dist[t] == -1:
            dist[t] = dist[s] + t_dist
            dfs_stack.append(t)
for _ in range(Q):
    x,y = map(int,input().split())
    print(dist[x]+dist[y])

Solution (Python):
from heapq import heappush, heappop
inf = float('inf')


def dijkstra(start,ad):
    global dist
    dist = [inf]*len(ad)
    dist[start] = 0
    pq = [(start,0)]
    while pq:
        v = heappop(pq)[0]
        for nv,nw in ad[v]:
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq,(nv,dist[nv]))

N = int(input())
ad = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1
    ad[a].append((b,c))
    ad[b].append((a,c))
Q,K = map(int,input().split())
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

dijkstra(K,ad)

for x, y in query:
    ans = dist[x] + dist[y]
    print(ans)

Solution (Python):
from heapq import heappush, heappop
inf = float('inf')



def dijkstra(ad,dist,n,start):
    pq = [(0,start)]
    while pq:
        w,v = heappop(pq)
        for nw,nv in ad[v]:
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq,(dist[nv],nv))

N = int(input())

ad = [[] for _ in range(N)]

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

Q,K = map(int,input().split())
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

dist = [inf]*N
dist[K] = 0

dijkstra(ad,dist,N,K)

for x,y in query:
    ans = dist[x] + dist[y]
    print(ans)

Solution (Python):
n = int(input())
edge = []
for _ in range(n-1):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,c])
q, k = map(int,input().split())
querry = []
for _ in range(q):
    x,y = map(int,input().split())
    querry.append([x-1,y-1])
    

class Graph():
    def __init__(self,n,edge):
        self.n = n
        self.edge = edge
        self.ed_list = [[] for _ in range(n)]
        for a,b,c in edge:
            self.ed_list[a].append([b,c])
            self.ed_list[b].append([a,c])
    
    def dijkstra(self,start):
        INF = float('inf')
        cost = [INF]*self.n
        cost[start] = 0
        from heapq import heappop,heappush
        stack = [[0, start]]
        while stack:
            c, x = heappop(stack)
            for to,j in self.ed_list[x]:
                if cost[to] > j + c:
                    cost[to] = j + c
                    heappush(stack,[j + c, to])
        return cost

gp = Graph(n,edge)
cost = gp.dijkstra(k-1)
for i,j in querry:
    print(cost[i] + cost[j])

Solution (Python):
n = int(input())
edge = [list(map(int,input().split())) for _ in range(n-1)]
q, k = map(int,input().split())
querry = [list(map(int,input().split())) for _ in range(q)]
INF = float('inf')
from heapq import heappush,heappop
def dijkstra(n,edge,start):
    ed_list = [[] for _ in range(n)]
    for a,b,c in edge:
        ed_list[a-1].append([b-1,c])
        ed_list[b-1].append([a-1,c])
    cost = [INF]*n
    cost[start] = 0
    stack =[[0,start]]
    while stack:
        c, x = heappop(stack)
        for i,j in ed_list[x]:
            if cost[i] > c + j:
                cost[i] = c + j
                heappush(stack,[c + j, i])
    return cost
arr_cost = dijkstra(n,edge,k-1)
for i,j in querry:
    print(arr_cost[i-1] + arr_cost[j-1])

Solution (Python):
from collections import *
from heapq import*
import sys
input=sys.stdin.readline
d=defaultdict(list)
n=int(input())
 
for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])

 
def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
 
q,k=map(int,input().split())
y=DIJKSTRA(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Solution (Python):
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

n=int(input())
d=[[]for _ in[0]*-~n]

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


def DIJKSTRA(point,d):
    cost      = [float("inf") for _ in range(len(d))]
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

q,k=map(int,input().split())
y=DIJKSTRA(k,d)

for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Solution (Python):
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

n=int(input())
d=[[]for _ in[0]*-~n]

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


def DIJKSTRA(point,d):
    cost      = [float("inf") for _ in range(len(d))]
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

q,k=map(int,input().split())
y=DIJKSTRA(k,d)

for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

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

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

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

dist = [-1] * N
dist[K] = 0


def dfs(n):
    for to, cost in T[n]:
        if dist[to] < 0:
            dist[to] = dist[n] + cost
            dfs(to)


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