CodeEff/ECCO huggingface dataset:
# Original solution
from collections import deque

n = int(eval(input()))

nodes = [set() for i in range(n+1)]
dis = [dict() for i in range(n+1)]
ans = [-1 for i in range(n+1)]

for _ in range(n-1):
    a,b,c = list(map(int,input().split()))
    nodes[a].add(b)
    nodes[b].add(a)
    dis[a][b] = c
    dis[b][a] = c

#print(nodes)
#print(dis)

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

q = [K]
d = 0
ans[K] = 0
c = 0
while True:
    now = q[-1]
    nex = -1
    for x in nodes[now]:
        if ans[x] == -1:
            nex = x
            break
    if nex == -1:
        if c >= n-1:
            break
        else:
            q.pop()
            d -= dis[now][q[-1]]

    else:
        nodes[now].remove(nex)
        nodes[nex].remove(now)
        d += dis[now][nex]
        q.append(nex)
        ans[nex] = d
        c += 1

#print(ans)

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


# Optimized solution
import sys
sys.setrecursionlimit(10**8)

N = int(eval(input()))

vertex = [{} for _ in range(N)]

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

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

d = [0 for i in range(N)]

def dfs(v1,v2):
    d[v2] = d[v1] + vertex[v1][v2]
    for v in vertex[v2]:
        if v == v1:
            continue
        dfs(v2,v)

for v in list(vertex[K-1].keys()):
    dfs(K-1,v)

for q in range(Q):
    x,y = list(map(int,input().split()))
    print((d[x-1] + d[y-1]))
# Original solution
import sys
from collections import deque
readline = sys.stdin.readline
n = int(readline())
D = [[-1]*n for _ in range(n)]
for i in  range(n): D[i][i]=0
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c = [int(x)-1 for x in list(map(int, readline().split()))]
    G[a].append(b)
    G[b].append(a)
    D[a][b] = c+1
    D[b][a] = c+1

q, k = list(map(int, readline().split()))
k -= 1
que = deque([k])
_D = [-1]*n
_D[k] = 0
while que:
    nw = que.popleft()
    d = _D[nw]
    for nx in G[nw]:
        if nw!=k and _D[nx]!=-1: continue
        _D[nx] = d+D[nw][nx]
        que.append(nx)

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

# Optimized solution
import sys
sys.setrecursionlimit(pow(10,6))
readline = sys.stdin.readline

def dfs(nw, d):
    V[nw] = d
    for nx in G[nw]:
        if V[nx[0]]==-1:
            dfs(nx[0], d+nx[1])

n = int(readline())
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c = list(map(int, readline().split()))
    G[a-1].append((b-1,c))
    G[b-1].append((a-1,c))
q, k = list(map(int, readline().split()))

V = [-1]*n
dfs(k-1, 0)

for i in range(q):
    x,y = [int(x)-1 for x in readline().split()]
    print((V[x]+V[y]))
# Original solution
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ts = collections.defaultdict(list)
    tc = collections.defaultdict(int)
    for i in range(n-1):
        ta, te, ttc = list(map(int, input().rstrip('\n').split()))
        ts[ta - 1] += [te - 1]
        ts[te - 1] += [ta - 1]
        tc[ta - 1, te - 1] = ttc
        tc[te - 1, ta - 1] = ttc

    q, k = list(map(int, input().rstrip('\n').split()))
    ql = [[0, k-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    while True:
        if len(ql) != 0:
            cost, p = ql.popleft()
            for v in ts[p]:
                if v not in fq:
                    n_cost = tc[p, v]
                    ql.append([cost + n_cost, v])
                    fq[v] = cost + n_cost
                else:
                    n_cost = tc[p, v]
                    if n_cost + cost < fq[v]:
                        ql.append([cost + n_cost, v])
                        fq[v] = cost + n_cost
        else:
            break
    for i in range(q):
        x, y = list(map(int, input().rstrip('\n').split()))
        print((fq[x-1] + fq[y-1]))


if __name__ == '__main__':
    solve()


# Optimized solution
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    tmd = collections.defaultdict(list)
    tmdc = collections.defaultdict(int)
    for i in range(n-1):
        tma, tmb, tmc = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
        tmdc[tma-1, tmb-1] = tmc
        tmdc[tmb-1, tma-1] = tmc

    q, k = list(map(int, input().rstrip('\n').split()))
    ql = [[0, k-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[k-1]
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq or cost + tmdc[tmp, tmv] < fq[tmv]:
                    ql.append([cost + tmdc[tmp, tmv], tmv])
                    fq[tmv] = cost + tmdc[tmp, tmv]
        else:
            break
    for i in range(q):
        x, y = list(map(int, input().rstrip('\n').split()))
        print((fq[x-1] + fq[y-1]))


if __name__ == '__main__':
    solve()
# Original solution
import sys
sys.setrecursionlimit(10**7)

n = int(eval(input()))
l = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c = list(map(int, input().split()))
  l[a-1].append([b-1, c])
  l[b-1].append([a-1, c])
q, k = list(map(int, input().split()))
dist = [-1]*n
dist[k-1] = 0
def dfs(v):
  for nv, c in l[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v]+c
      dfs(nv)
dfs(k-1)
for _ in range(q):
  x, y = list(map(int, input().split()))
  print((dist[x-1] + dist[y-1]))

# Optimized solution
import sys
sys.setrecursionlimit(10**7)

n = int(eval(input()))
l = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c = list(map(int, input().split()))
  l[a-1].append((b-1, c))
  l[b-1].append((a-1, c))
q, k = list(map(int, input().split()))
dist = [-1]*n
dist[k-1] = 0
def dfs(v):
  for nv, c in l[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v]+c
      dfs(nv)
dfs(k-1)
for _ in range(q):
  x, y = list(map(int, input().split()))
  print((dist[x-1] + dist[y-1]))
# Original solution
import sys
sys.setrecursionlimit(10**9)

n = int(eval(input()))
adjacency = [[] for i in range(n+1)] #adjacency[i]は頂点iと隣接する頂点のリスト
distance = {} # distance[(i,j)](i,jは隣接した頂点)は頂点i,jを結ぶ辺の長さ
for i in range(n-1):
    line = list(map(int, input().split()))
    adjacency[line[0]].append(line[1])
    adjacency[line[1]].append(line[0])
    distance[(line[0], line[1])] = line[2]
    distance[(line[1], line[0])] = line[2]
q, k = list(map(int, input().split()))
x = []
y = []
for i in range(q):
    line = list(map(int, input().split()))
    x.append(line[0])
    y.append(line[1])

k_distance = [-1 for i in range(n+1)] # k_distance[i]は頂点i,kの距離
k_distance[k] = 0
reached = {k}
def dfs(v, d): # 現在いる頂点vと頂点v,k間の距離dを入力すると頂点vと隣接する未到達の頂点のk_distanceを計算してappendする
    for neighbor in adjacency[v]:
        if not neighbor in reached:
            reached.add(neighbor)
            k_distance[neighbor] = d + distance[(v, neighbor)]
            dfs(neighbor, k_distance[neighbor])
    return
dfs(k, 0)
for i in range(q):
    print((k_distance[x[i]] + k_distance[y[i]]))


# Optimized solution
import sys
sys.setrecursionlimit(10**6)
from sys import stdin
input = stdin.readline

n = int(eval(input()))
adjacency = [[] for i in range(n+1)] #adjacency[i]は頂点iと隣接する頂点のリスト
distance = {} # distance[(i,j)](i,jは隣接した頂点)は頂点i,jを結ぶ辺の長さ
for i in range(n-1):
    line = list(map(int, input().split()))
    adjacency[line[0]].append(line[1])
    adjacency[line[1]].append(line[0])
    distance[(line[0], line[1])] = line[2]
    distance[(line[1], line[0])] = line[2]
q, k = list(map(int, input().split()))
x = []
y = []
for i in range(q):
    line = list(map(int, input().split()))
    x.append(line[0])
    y.append(line[1])

k_distance = [-1 for i in range(n+1)] # k_distance[i]は頂点i,kの距離
k_distance[k] = 0
reached = {k}
def dfs(v, d): # 現在いる頂点vと頂点v,k間の距離dを入力すると頂点vと隣接する未到達の頂点のk_distanceを計算してappendする
    for neighbor in adjacency[v]:
        if not neighbor in reached:
            reached.add(neighbor)
            k_distance[neighbor] = d + distance[(v, neighbor)]
            dfs(neighbor, k_distance[neighbor])
    return
dfs(k, 0)
for i in range(q):
    print((k_distance[x[i]] + k_distance[y[i]]))
# Original solution
import heapq
N = int(eval(input()))
es = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))
Q,K = list(map(int, input().split()))
K -= 1

INF = float('inf')
ds = [INF for i in range(N)]
ds[K] = 0
visited = [0 for i in range(N)]
q = [K]
heapq.heapify(q)
while q:
    now = heapq.heappop(q)
    visited[now] = 1
    for to,cost in es[now]:
        ds[to] = min(ds[to], ds[now]+cost)
        if visited[to]: continue
        heapq.heappush(q,to)

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


# Optimized solution
import heapq
N = int(eval(input()))
src = [tuple(map(int,input().split())) for i in range(N-1)]
Q,K = list(map(int,input().split()))
K -= 1
qs = [tuple(map(int,input().split())) for i in range(Q)]

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

INF = float('inf')
dists = [INF] * N
dists[K] = 0
hq = [(0,K)]
heapq.heapify(hq)

while hq:
    dist,v = heapq.heappop(hq)
    dists[v] = dist
    for dd,to in es[v]:
        if dists[to] != INF: continue
        heapq.heappush(hq, (dist+dd, to))

for a,b in qs:
    a,b = a-1,b-1
    print((dists[a] + dists[b]))
# Original solution
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

@lru_cache(maxsize=1000)
def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

N = int(eval(input()))

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

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

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

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

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

# Optimized solution
import sys
sys.setrecursionlimit(10**6)
def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

N = int(eval(input()))

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

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

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

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

for _ in range(Q):
    x, y = list(map(int, input().split()))
    print((depth[x-1] + depth[y-1]))
# Original solution
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(eval(input()))
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
q, k = list(map(int, input().split()))
k -= 1
shortest = []
for i in range(n):
    shortest.append(dijkstra(adj, n, i))
for i in range(q):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1
    print((shortest[x][k] + shortest[y][k]))

# Optimized solution
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(eval(input()))
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
q, k = list(map(int, input().split()))
shortest = dijkstra(adj, n, k - 1)
for i in range(q):
    x, y = list(map(int, input().split()))
    print((shortest[x - 1] + shortest[y - 1]))
# Original solution
n=int(eval(input()))
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=list(map(int,input().split()))
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
ans=[-1]*n
q,k=list(map(int,input().split()))
ans[k-1]=0
from collections import deque
d=deque([k-1])
while d:
  now=d.pop()
  for x in l[now]:
    a,b=x
    if ans[a]<0:
      ans[a]=ans[now]+b
      d.appendleft(a)
for i in range(q):
  a,b=list(map(int,input().split()))
  print((ans[a-1]+ans[b-1]))

# Optimized solution
import sys
from collections import deque
input = sys.stdin.readline
n=int(eval(input()))
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=list(map(int,input().split()))
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
ans=[-1]*n
q,k=list(map(int,input().split()))
ans[k-1]=0
d=deque([k-1])
while d:
  now=d.pop()
  for x in l[now]:
    a,b=x
    if ans[a]<0:
      ans[a]=ans[now]+b
      d.appendleft(a)
for i in range(q):
  a,b=list(map(int,input().split()))
  print((ans[a-1]+ans[b-1]))
# Original solution
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return list(map(int, input().split()))
N = int(eval(input()))

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

D = [0] * (N+1)
Q, K = inpl()
DQ = deque([K])
visited = [False]*(N+1)

while DQ:
    p = DQ.popleft()
    visited[p] = True
    for q, c in G[p]:
        if not visited[q]:
            D[q] = D[p] + c
            DQ.append(q)

for _ in range(Q):
    x, y = inpl()
    print((D[x] + D[y]))

# Optimized solution
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return list(map(int, input().split()))
N = int(eval(input()))

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

Q, K = inpl()

def BFS(G, K):
    DQ = deque([K])
    D = [0] * (N+1)
    visited = [False]*(N+1)
    while DQ:
        p = DQ.popleft()
        visited[p] = True
        for q, c in G[p]:
            if not visited[q]:
                D[q] = D[p] + c
                DQ.append(q)
    return D

D = BFS(G, K)
for _ in range(Q):
    x, y = inpl()
    print((D[x] + D[y]))
# Original solution
import sys
sys.setrecursionlimit(1000000)
n=int(eval(input()))
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=list(map(int,input().split()))
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
q,k=list(map(int,input().split()))
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=list(map(int,input().split()))
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)


# Optimized solution
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)
n=int(eval(input()))
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=list(map(int,input().split()))
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
q,k=list(map(int,input().split()))
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=list(map(int,input().split()))
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)
# Original solution
N = int(eval(input()))
M = N-1
inf = float("inf")
dp = [[inf]*N for _ in [0]*N]
for i in range(N):dp[i][i] = 0
q = [list(map(int, input().split())) for i in range(M)]
Q , K = list(map(int, input().split()))
p = [list(map(int, input().split())) for i in range(Q)]
ans = 0
 
for a,b,c in q:
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])
for a,b in p:
    print((dp[a-1][K-1]+dp[K-1][b-1]))



# Optimized solution
N = int(eval(input()))
tree = [[] for _ in range(N)]

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

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

depth = [0 for _ in range(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    # 空のシーケンスは偽になる
    while St:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

for i in range(Q):
    x, y = list(map(int, input().split()))
    x -= 1; y -= 1
    print((depth[x] + depth[y]))
# Original solution
import queue

N = int(eval(input()))
tree = [[] for _ in range(N)]

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

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

depth = [0 for _ in range(N)]

def bfs(v, p = -1, d = 0):
    q = queue.Queue()
    q.put([v, p, d])
    while not q.empty():
        cur = q.get()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            q.put([i, cur[0], cur[2] + j])

bfs(K)

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

# Optimized solution

from collections import deque

N = int(eval(input()))
tree = [[] for _ in range(N)]

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

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

depth = [0 for _ in range(N)]

def bfs(v, p = -1, d = 0):
    q = deque()
    q.append([v, p, d])
    while len(q)>0:
        cur = q.popleft()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            q.append([i, cur[0], cur[2] + j])

bfs(K)

for i in range(Q):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1
    print((depth[x] + depth[y]))
# Original solution
import heapq
N = int(eval(input()))
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    G[a - 1].append([c, b - 1])
    G[b - 1].append([c, a - 1])
Q, K = list(map(int, input().split()))

def dijkstra(s, N, G, x, y):
    d = [20 ** 9] * N
    d[s] = 0
    hq = [[0, s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        v, i = heapq.heappop(hq)
        if d[i] < v:
            continue
        for c, j in G[i]:
            if d[j] > d[i] + c:
                d[j] = d[i] + c
                heapq.heappush(hq, [d[j], j])
    return d[x] + d[y]

dist = [0] * Q
for i in range(Q):
    x, y = list(map(int, input().split()))
    dist[i] = dijkstra(K - 1, N, G, x - 1, y - 1)

for d in dist:
    print(d)

# Optimized solution
import heapq
N = int(eval(input()))
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    G[a - 1].append([c, b - 1])
    G[b - 1].append([c, a - 1])
Q, K = list(map(int, input().split()))

def dijkstra(s, N, G):
    d = [float('inf')] * N
    d[s] = 0
    hq = [[0, s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        v, i = heapq.heappop(hq)
        if d[i] < v:
            continue
        for c, j in G[i]:
            if d[j] > d[i] + c:
                d[j] = d[i] + c
                heapq.heappush(hq, [d[j], j])
    return d

D = dijkstra(K - 1, N, G)

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

for d in dist:
    print(d)
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**5
n = int(eval(input()))

graph = [[] for _ in range(n+1)]
d = [[INF]*(n+1) for _ in range(n+1)]

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

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


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

dfs(k, -1, 0)

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


# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**9+1
n = int(eval(input()))
graph = [[] for _ in range(n+1)]

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

q, k = list(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 = list(map(int, input().split()))
    print((dist[x]+dist[y]))
# Original solution
import sys
import heapq
input = sys.stdin.readline
n = int(eval(input()))
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))
INF = float('inf')


def dijkstra(init_v):
    dist = [INF]*n
    dist[init_v] = 0
    tasks = [(0, init_v)]
    while tasks:
        d, v = heapq.heappop(tasks)
        if dist[v] < d:
            continue
        for d2, v2 in edges[v]:
            if dist[v2] <= dist[v]+d2:
                continue
            dist[v2] = dist[v]+d2
            heapq.heappush(tasks, ((dist[v2], v2)))
    return dist


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

# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(eval(input()))
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))
INF = float('inf')


def dfs(v, parent, distance):
    dist[v] = distance
    for d, v2 in edges[v]:
        if parent == v2:
            continue
        dfs(v2, v, distance+d)


q, k = list(map(int, input().split()))
dist = [INF]*n
dfs(k-1, -1, 0)
for _ in range(q):
    x, y = [int(x)-1 for x in input().split()]
    print((dist[x]+dist[y]))