CodeEff/ECCO huggingface dataset:
# Original solution
def f(n):
    for k, c in list(dic.items()):
        a, b = k
        if a == n:
            if not b in cost or c < cost[b]:
                cost[b] = c
        elif b == n:
            if not a in cost or c < cost[a]:
                cost[a] = c
    for k, c in sorted(list(cost.items()), key=lambda x: x[1]):
        if not k in res:
            res.append(k)
            ans.append(c)
            f(k)
while True:
    n, m = list(map(int, input().split()))
    if n == m == 0: break
    dic = {}
    s, b, c = list(map(int, input().split()))
    dic[(s, b)] = c
    for i in range(m-1):
        a, b, c = list(map(int, input().split()))
        dic[(a, b)] = c
    cost = {}
    res = [s]
    ans = []
    f(s)
    print(sum(ans))

# Optimized solution
def f(n, ans):
    for k, c in list(dic.items()):
        a, b = k
        if a == n:
            if not b in cost or c < cost[b]:
                cost[b] = c
        elif b == n:
            if not a in cost or c < cost[a]:
                cost[a] = c
    for k, c in sorted(list(cost.items()), key=lambda x: x[1]):
        if not k in res:
            res.append(k)
            ans += c
            del cost[k]
            return f(k, ans)
    return ans
            
while True:
    n, m = list(map(int, input().split()))
    if n == m == 0: break
    dic = {}
    s, b, c = list(map(int, input().split()))
    dic[(s, b)] = c
    for i in range(m-1):
        a, b, c = list(map(int, input().split()))
        dic[(a, b)] = c
    cost = {}
    res = [s]
    print(f(s, 0))
# Original solution
def f(s, cost, route, ans):
    route.append(s)
    ans += cost[s]
    del cost[s]
    for k, c in list(data.items()):
        a, b = k
        if s == a:
            if not b in route:
                if not b in cost or c < cost[b]:
                    cost[b] = c
        elif s == b:
            if not a in route:
                if not a in cost or c < cost[a]:
                    cost[a] = c
    if cost:
        s = sorted(list(cost.items()), key=lambda x: x[1])[0][0]
        return f(s, cost, route, ans)
    else:
        return ans

while True:
    n, m = list(map(int, input().split()))
    if n == m == 0: break
    data = {}
    for i in range(m):
        a, b, c = list(map(int, input().split()))
        data[(a, b)] = c
    else:
        print(f(0, {0:0}, [], 0))

# Optimized solution
def f(s, cost, route, ans):
    route.append(s)
    ans += cost[s]
    del cost[s]
    for k, c in list(data.items()):
        if s in k:
            a, b = k
            b = b if s == a else a
            if not b in route:
                if not b in cost or c < cost[b]:
                    cost[b] = c
    if cost:
        s = sorted(list(cost.items()), key=lambda x: x[1])[0][0]
        return f(s, cost, route, ans)
    else:
        return ans

while True:
    n, m = list(map(int, input().split()))
    if n == m == 0: break
    data = {}
    for i in range(m):
        a, b, c = list(map(int, input().split()))
        data[(a, b)] = c
    else:
        print(f(0, {0:0}, [], 0))
# Original solution
m=list(map(int, input().split()))
m.sort()
print(' '.join(map(str, m)))

# Optimized solution
a=list(map(int,input().split()));a.sort();print(a[0],a[1],a[2])
# Original solution
#!/usr/bin/env python
# coding: utf-8

def main():
	values = [int(x) for x in input().split(" ")]
	if values[0] > values[1]:
		values[0], values[1] = values[1], values[0]
	if values[1] > values[2]:
		values[1], values[2] = values[2], values[1]
	if values[0] > values[1]:
		values[0], values[1] = values[1], values[0]
	print("%s %s %s" % tuple(values))

if __name__ == '__main__':
	main()

# Optimized solution
if __name__ == '__main__':
    a, b, c = list(map(int, input().split()))
    if a < b:
        if b < c:
            print(a, b, c)
        elif a < c:
            print(a, c, b)
        else:
            print(c, a, b)
    else:
        if a < c:
            print(b, a, c)
        elif b < c:
            print(b, c, a)
        else:
            print(c, b, a)
# Original solution
print((" ".join(map(str,sorted([int(i) for i in input().split(" ")])))))

# Optimized solution
# encoding:utf-8

input = list(map(int, input().split()))
input.sort()

print((" ".join(map(str, input))))
# Original solution
#coding:utf-8
import sys
 
abc=sys.stdin.readline()
nums=abc.split( ' ' )
for i in range( len( nums) ):
	nums[i] = int( nums[i] )
nums.sort()
print(( "{} {} {}".format( nums[0], nums[1], nums[2] ) ))

# Optimized solution
import sys

nums = [ int( val ) for val in sys.stdin.readline().split( " " ) ]
nums = sorted( nums )
print(( "{:d} {:d} {:d}".format( nums[0], nums[1], nums[2] ) ))
# Original solution
x=input().split()
y=list(map(int,x))
a=y[0]
b=y[1]
c=y[2]
d=sorted([a,b,c])
print(("{0} {1} {2}".format(d[0],d[1],d[2])))

# Optimized solution
a,b,c=list(map(int,input().split()))
d=[a,b,c]
d.sort()
print(("{0} {1} {2}".format(d[0],d[1],d[2])))
# Original solution
nums = input().split()
nums = list(map(int, nums))

nums.sort()

print((' '.join(list(map(str, nums)))))

# Optimized solution
a = sorted(list(map(int, input().split())))
print((' '.join(map(str, a))))
# Original solution
xs=list(map(int,input().split()))
print((' '.join(map(str, sorted(xs)))))

# Optimized solution
input_list = list(map(int, input().split()))
print((' '.join(map(str, sorted(input_list)))))
# Original solution
a,b,c=list(map(int,input().split()))
if(a>b):
 tmp=a
 a=b
 b=tmp
if(b>c):
 tmp=b
 b=c
 c=tmp
if(a>b):
 tmp=a
 a=b
 b=tmp
print(a,b,c)

# Optimized solution
a,b,c=list(map(int,input().split()))
if(a>b):
 tmp=a
 a=b
 b=tmp
if(b>c):
 tmp=b
 b=c
 c=tmp
if(a>b):
 tmp=b
 b=a
 a=tmp
print(str(a)+" "+str(b)+" "+str(c))
# Original solution
a = list(map(int, input().split()))
for i in range(len(a)):
    j = len(a) - 1
    while i < j:
        if a[j] < a[j-1]:
            t = a[j]
            a[j] = a[j-1]
            a[j-1] = t
        j -= 1

for i in range(len(a)):
    if i == len(a) - 1:
        print(a[i])
    else:
        print(a[i], end=" ")
        


# Optimized solution
n = [int(i) for i in input().split()]
n = sorted(n)
for i in range(3):
    if i == 2:
        print(n[i])
    else:
        print(n[i], end = " ")
# Original solution
s = input()
nlist = list(map(int, s.split()))
a, b, c= nlist

if a<b:
    if b<c:
        print('%d %d %d' %(a, b, c))
    elif c<a:
        print('%d %d %d' %(c, a, b))
    else:
        print('%d %d %d' %(a, c, b))
else:
    if a<c:        
        print('%d %d %d' %(b, a, c))
    elif c<b:
        print('%d %d %d' %(c, b, a))
    else:
        print('%d %d %d' %(b, c, a))

# Optimized solution
s = input()
nlist = list(map(int, s.split()))
a, b, c= nlist
#print nlist.sort() 
ls = sorted(nlist)
print('%d %d %d' %(ls[0], ls[1], ls[2]))
# Original solution
from collections import deque
n= int(eval(input()))
tab = [[0 for _ in range(n)] for _ in range(n)]
branchdict = {}
for i in range(n-1):
    a,b,c= list(map(int,input().split()))
    tab[a-1][b-1] = c
    tab[b-1][a-1] = c
    branchdict[a-1] = branchdict.get(a-1,[]) + [b-1]
    branchdict[b-1] = branchdict.get(b-1,[]) + [a-1]
q,k= list(map(int,input().split()))
start = k-1
que = deque()
que.append(start)
passed = set()
passed.add(start)
cost = [0] * n
while len(que)!=0:
    node = que.pop()
    for abr in branchdict[node]:
        if not abr in passed:
            cost[abr] = cost[node] + tab[node][abr]
            passed.add(abr)
            que.append(abr)
for i in range(q):
    x,y= list(map(int,input().split()))
    print((cost[x-1]+cost[y-1]))

# Optimized solution
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n= int(eval(input()))
bd = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c= list(map(int,input().split()))
    bd[a-1].append((b-1,c))
    bd[b-1].append((a-1,c))
q,k= list(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= list(map(int,input().split()))
    print((cost[x-1]+cost[y-1]))
# Original solution
N = int(eval(input()))
E = [set() for _ in range(N)]
C = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
  a,b,c = list(map(int,input().split()))
  E[a-1].add(b-1)
  E[b-1].add(a-1)
  C[a-1][b-1] = c
  C[b-1][a-1] = c
Q,K = list(map(int,input().split()))
K -= 1
Query = []
for i in range(Q):
  x,y = list(map(int,input().split()))
  Query.append([x-1,y-1])
#print(E)
#print(C)
#print(K)
#print(Query)

Kcost = [0 for _ in range(N)]
def dfs(u,v):
  if v != -1:
    Kcost[u] = Kcost[v] + C[u][v]
  for t in E[u]:
    if t != K and Kcost[t] == 0:
      dfs(t,u)
dfs(K,-1)

for x,y in Query:
  print((Kcost[x]+Kcost[y]))

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

N = int(eval(input()))
E = [set() for _ in range(N)]
C = {}
for i in range(N-1):
  a,b,c = list(map(int,input().split()))
  E[a-1].add(b-1)
  E[b-1].add(a-1)
  C[min(a-1,b-1)*N+max(a-1,b-1)] = c
  
Q,K = list(map(int,input().split()))
K -= 1
Query = []
for i in range(Q):
  x,y = list(map(int,input().split()))
  Query.append([x-1,y-1])
#print(E)
#print(C)
#print(K)
#print(Query)

Kcost = [0 for _ in range(N)]
def dfs(u,v):
  if v != -1:
    Kcost[u] = Kcost[v] + C[min(u,v)*N+max(u,v)]
  for t in E[u]:
    if t != K and Kcost[t] == 0:
      dfs(t,u)
dfs(K,-1)

for x,y in Query:
  print((Kcost[x]+Kcost[y]))
# Original solution
n=int(eval(input()))
INF=9999999999
d=[INF for _ in range(n)]
dist=[[INF for _ in range(n)] for _ in range(n)]
linked=[[] for _ in range(n)]

for i in range(n):
    dist[i][i]=0

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

def dfs(v,p,dv):
    d[v]=dv
    for i in linked[v]:
        linked[i].remove(v)
        if(i==p):
            continue
        dfs(i,v,dv+dist[v][i])



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

dfs(k-1,-1,0)

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




# Optimized solution
import sys
sys.setrecursionlimit(10**6)
n=int(eval(input()))
INF=9999999999
d=[INF for _ in range(n)]
g=[[] for _ in range(n)]


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

def dfs(v,p,dv):
    d[v]=dv
    for gi,c in g[v]:
        if(gi==p):
            continue
        dfs(gi,v,dv+c)

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

dfs(k-1,-1,0)

for i in range(q):
    x,y=list(map(int,input().split()))
    print((d[x-1]+d[y-1]))
# Original solution
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return list(map(int,input().split()))
def lmp(): return list(map(int,input().split()))

n=int(eval(input()))
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append((b,c))
    tree[b].append((a,c))
q,k=mp()
dist=[-1]*(n+1)
dist[k]=0
deq=deque()
deq.append(k)

while len(list(deq))>0:
    p=deq.popleft()
    for x,y in tree[p]:
        if dist[x]==-1:
            dist[x]=dist[p]+y
            deq.append(x)
for i in range(q):
    xi,yi=mp()
    print((dist[xi]+dist[yi]))

# Optimized solution
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return list(map(int,input().split()))
def lmp(): return list(map(int,input().split()))

n=int(eval(input()))
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append((b,c))
    tree[b].append((a,c))
q,k=mp()
dist=[-1]*(n+1)
dist[k]=0
deq=deque()
deq.append(k)

while len(deq):
    p=deq.popleft()
    for x,y in tree[p]:
        if dist[x]==-1:
            dist[x]=dist[p]+y
            deq.append(x)
for i in range(q):
    xi,yi=mp()
    print((dist[xi]+dist[yi]))
# Original solution
import sys
sys.setrecursionlimit(10**8)
N = int(eval(input()))
a = [[] for i in range(N)]
for i in range(N-1):
  A, B, C = list(map(int, input().split()))
  a[A-1].append([B-1, C])
  a[B-1].append([A-1, C])
dist = [-1]*N
Q, K = list(map(int, input().split()))
dist[K-1] = 0

def dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = list(map(int, input().split()))
    print((dist[x-1]+dist[y-1]))
  #print(*ans, sep = "\n")

if __name__ == "__main__":
  main()

# Optimized solution
import sys
sys.setrecursionlimit(10**8)
N = int(input())
a = [[] for i in range(N)]
for i in range(N-1):
  A, B, C = map(int, input().split())
  a[A-1].append([B-1, C])
  a[B-1].append([A-1, C])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    ans.append(dist[x-1]+dist[y-1])
  print(*ans, sep = "\n")

if __name__ == "__main__":
  main()
# Original solution
N = int(eval(input()))
INF = float("inf")
es = [[INF for _ in range(N)] for _ 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][b] = c
    es[b][a] = c

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

checked = [False] * N

d = [INF] * N
d[K-1] = 0
def dijkstra(s):
    while True:
        v = -1
        for i in range(N):
            if checked[i] == False and v == -1:
                v = i
            elif checked[i] == False and d[i] < d[v]:
                v = i
        if v == -1:
            break
        
        checked[v] = True
        for i in range(N):
            d[i] = min(d[i], d[v] + es[v][i])
    return

dijkstra(K-1)

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


# Optimized solution
N = int(eval(input()))
INF = float("inf")
es = [[] for _ 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()))
xy = []
for i in range(Q):
    x,y = list(map(int, input().split()))
    xy.append([x-1, y-1])

checked = [False] * N
d = [INF] * N
d[K-1] = 0

next_check = []
next_check.append(K-1)
while len(next_check):
    now = next_check.pop()
    for next,cost in es[now]:
        if not checked[next]:
            d[next] = min(d[next], d[now] + cost)
            checked[next] = True
            next_check.append(next)
    


for x,y in xy:
    print((d[x] + d[y]))
# Original solution
n = int(eval(input()))
path = [[0 for i in range(n)] for j in range(n)]

for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    path[min(a-1, b-1)][max(a-1, b-1)] = c


q, k = list(map(int, input().split()))
distance = [None] * n
distance[k-1] = 0
queue = [k-1]
while(len(queue)):
    p = queue.pop()
    for i in range(n):
        if(path[min(i,p)][max(i,p)]!=0 and distance[i] == None):
            distance[i] = distance[p] + path[min(i,p)][max(i,p)]
            queue.append(i)

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


# Optimized solution
n = int(eval(input()))
path = [[] for i in range(n)]

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


q, k = list(map(int, input().split()))
distance = [None] * n
distance[k-1] = 0
queue = [k-1]
while(len(queue)):
    p = queue.pop()
    for i,c in path[p]:
        if(distance[i] == None):
            distance[i] = distance[p] + c
            queue.append(i)

for i in range(q):
    x, y = list(map(int, input().split()))
    print((distance[x-1]+distance[y-1]))
# Original solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N = int(eval(input()))
query = [[0]*N for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1][b-1] = c
    query[b-1][a-1] = c

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in enumerate(lis):
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print((dist[x-1]+dist[y-1]))

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N = int(eval(input()))
query = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1].append((b-1, c))
    query[b-1].append((a-1, c))

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print((dist[x-1]+dist[y-1]))
# Original solution
import sys

TO_K = []
TREE = []
DISTANCE = []

def dfs(child, parent):
    TO_K[child] = TO_K[parent] + DISTANCE[parent][child]

    for i_gch in TREE[child]:
        if i_gch == parent:
            continue
        dfs(i_gch, child)

    return


def main():
    n = int(eval(input()))
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = list(map(int, input().split()))
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    global DISTANCE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    DISTANCE = [[0]*(n+1) for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append(b)
        TREE[b].append(a)
        DISTANCE[a][b] = c
        DISTANCE[b][a] = c

    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)

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

TO_K = []
TREE = []
DISTANCE = []

def dfs(child, parent):
    for i_node in TREE[parent]:
        if i_node[0] == child:
            TO_K[child] = TO_K[parent] + i_node[1]

    for i_gch in TREE[child]:
        if i_gch[0] == parent:
            TO_K[child] = TO_K[parent] + i_gch[1]
        else:
            dfs(i_gch[0], child)

    return


def main():
    n = int(eval(input()))
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = list(map(int, input().split()))
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)
# Original solution
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)

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

graph = defaultdict(set)
for v, w, c in edges:
    graph[v].add((w, c))
    graph[w].add((v, c))

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
visited = [False] * (N + 1)

def dfs(v, p, d):    
    dp[v] = d
    visited[v] = True
    for j, c in graph[v]:
        if j == p or visited[j]:
            continue
        dfs(j, v, d + c)

dfs(K, 0, 0)

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


# Optimized solution
from collections import defaultdict
from heapq import heappop, heappush

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

graph = defaultdict(set)
for v, w, c in edges:
    graph[v].add((w, c))
    graph[w].add((v, c))

dp = [-1] * (N + 1)
pq = []

# Initialization
dp[K] = 0
heappush(pq, (0, K))

while pq:
    cost, u = heappop(pq)
    
    for w, c in graph[u]:
        if dp[w] > -1:
            continue

        dp[w] = dp[u] + c
        heappush(pq, (dp[w], w))

for _ in range(Q):
    x, y = list(map(int, input().split()))
    print((dp[x] + dp[y]))
# Original solution
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(eval(input()))

graph = [[mod for i in range(N)] for i in range(N)]

weights = {}

roots = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    roots[a].append(b)
    roots[b].append(a)
    weights[(a,b)] = c
    weights[(b,a)] = c

Q, K = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
    x, y = LI()
    x -= 1
    y -= 1
    xy[i] = [x, y]
"""
xyzで全部の通りを見つけるとN ** 3で無理
なので今回は木構造に注目してBFS or DFSで解いたらいいのでは？
"""

visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0

while len(queue)> 0:
    node = queue.popleft()
    cnt = visited[node]
    for n_node in roots[node]:
        if visited[n_node] == -1:
            visited[n_node] = cnt + weights[(node, n_node)]
            queue.append(n_node)
for x, y in xy:
    print((visited[x] + visited[y]))


# Optimized solution
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(eval(input()))
weights = {}

roots = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    roots[a].append(b)
    roots[b].append(a)
    weights[(a,b)] = c
    weights[(b,a)] = c

Q, K = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
    x, y = LI()
    x -= 1
    y -= 1
    xy[i] = [x, y]
"""
xyzで全部の通りを見つけるとN ** 3で無理
なので今回は木構造に注目してBFS or DFSで解いたらいいのでは？
重みを単純にグラフに持つと10**5 ** 2になってしまうので注意
"""

visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0

while len(queue)> 0:
    node = queue.popleft()
    cnt = visited[node]
    for n_node in roots[node]:
        if visited[n_node] == -1:
            visited[n_node] = cnt + weights[(node, n_node)]
            queue.append(n_node)

for x, y in xy:
    print((visited[x] + visited[y]))
# Original solution
from heapq import heappush,heappop
N = int(eval(input()))
table=[[]for i in range(N)]
for i in range(N-1):
    a,b,c=list(map(int,input().split()))
    table[a-1].append([b-1,c])
    table[b-1].append([a-1,c])
Q,K=list(map(int,input().split()))
Que=[[int(i) for i in input().split()] for i in range(Q)]
inf=10**17
dis=[inf]*N
dis[K-1]=0
kei=[]
heappush(kei,[0,K-1])
while kei:
    q,x=heappop(kei)
    if dis[x]<q:
        continue
    for i,d in table[x]:
        if dis[x]+d<dis[i]:
            dis[i]=dis[x]+d
            heappush(kei,[dis[i],i])
ans =[]
for x,y in Que:
    ans.append(dis[x-1]+dis[y-1])
print(('\n'.join(map(str,ans))))

# Optimized solution
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
N=int(eval(input()))
table=[[] 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
    table[a].append((b,c))
    table[b].append((a,c))
Q,K=list(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]))