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())
edges = [set() for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    edges[a].add((c, b))
    edges[b].add((c, a))
q, k = map(int, input().split())
stack = [(0, k, None)]
costs = [0] * (n + 1)
while stack:
    c, p, a = stack.pop()
    costs[p] = c
    stack.extend((c + c2, p2, p) for c2, p2 in edges[p] if p2 != a)

print('\n'.join(map(str, (costs[x] + costs[y] for x, y
                          in (map(int, input().split()) for _ in range(q))))))

Solution (Python):
n = int(input())
edges = [set() for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    edges[a].add((c, b))
    edges[b].add((c, a))
q, k = map(int, input().split())
stack = [(0, k, None)]
costs = [0] * (n + 1)
visited = set()
while stack:
    c, p, a = stack.pop()
    costs[p] = c
    visited.add(p)
    stack.extend((c + c2, p2, p) for c2, p2 in edges[p] if p2 != a)

print('\n'.join(map(str, (costs[x] + costs[y] for x, y
                          in (map(int, input().split()) for _ in range(q))))))

Solution (Python):
def dfs():
    sta = []
    ans = [-1]*(N+1)

    sta.append(K)
    ans[K] = 0

    while sta:
        nod = sta.pop()
        for t, d in tree[nod]:
            if ans[t] < 0:
                ans[t] = ans[nod] + d
                sta.append(t)

    return ans


N = int(input())
tree = [[] for i 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())
dis = dfs()

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

Solution (Python):
I=lambda:map(int,input().split());n,=I();G=[[]for i in[0]*-~n]
for i in G[2:]:a,b,c=I();G[a]+=(b,c),;G[b]+=(a,c),
q,k=I();s=[(k,0,0)]
while s:v,p,u=s.pop();s+=[(t,v,u+c)for t,c in G[v]if p-t];G[v]=u
for p in[0]*q:x,y=I();print(G[x]+G[y])

Solution (Python):



import numpy as np

n = raw_input()
n = int(n)

tree = []
for i in range(n):
    tree.append([])

for i in range(n-1):
    abc = raw_input()
    abc = abc.split()
    abc = map(int, abc)
    tree[abc[0]-1].append([abc[1]-1,abc[2]])
    tree[abc[1]-1].append([abc[0]-1,abc[2]])


qk = raw_input()
qk = qk.split()
q,k = map(int,qk)

question = []
for i in range(q):
    xy = raw_input()
    xy = xy.split()
    xy = map(int,xy)
    question.append(xy)

distance = []
for i in range(n):
    distance.append(-1)

distance[k-1] = 0

next_point = [k-1]

while 1:
    search_point = next_point
    next_point = []
    if len(search_point) == 0:
        break
    else:
        for i in search_point:
            for j in tree[i]:
                if distance[j[0]] == -1:
                    distance[j[0]] = distance[i] + j[1]
                    next_point.append(j[0])

for line in question:
    print distance[line[0]-1] + distance[line[1]-1]

Solution (Python):


N = int(input())
p =[]
for i in range(N-1):
    p.append(list(map(int, input().split())))
Q,K = list(map(int, input().split()))
r = []
for i in range(Q):
    r.append(list(map(int, input().split())))


adj = [[] for i in range(N+1)]
for pi in p:
    adj[pi[0]].append((pi[1],pi[2]))
    adj[pi[1]].append((pi[0],pi[2]))
adj


from collections import deque 
dist = [-1]*(N+1) 
dist[K] = 0 
d = deque() 
d.append(K)
while len(d):
    pp = d.popleft() 
    for q,c in adj[pp]:
        if dist[q] != -1:
            continue
        dist[q] = dist[pp]+c
        d.append(q)
for i in range(Q):
    x, y = r[i]
    print(dist[x]+dist[y])

Solution (Python):
from collections import deque

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

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

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

d = [-1] * (n + 1)
d[k] = 0
pq = deque()
pq.append(k)
while len(pq):
    u = pq.popleft()
    for v, w in g[u]:
        if d[v] != -1: continue
        d[v] = d[u] + w
        pq.append(v)

for i in range(q):
    u, v = [int(x) for x in input().split()]
    print(d[u] + d[v])

Solution (Python):

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

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

Q,K = map(int,input().split())
K -= 1
costs = [None]*N
costs[K] = 0

stack = [K]

while stack:
  s = stack.pop()
  c = costs[s]
  for t,d in E[s]:
    if costs[t] is None:
      costs[t] = c + d
      stack.append(t)

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

Solution (Python):

import sys
from collections import deque
import copy

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline




class point_node:
    def __init__(self, point, cost):
        self.point = point
        self.cost = cost

def  BFS(con_list, start_point):
    cost_list = {}
    cost_list[start_point] = 0

    node_list = deque([point_node(start_point, 0)])
    while 1:
        
        
        now_node = node_list.popleft()
        connects = con_list[now_node.point]
        for c in connects:
            if c[0] not in cost_list:
                cost_list[c[0]] = c[1] + now_node.cost
                node_list.append(point_node(c[0], c[1] + now_node.cost))
        if len(node_list) == 0:
            break
        

    return cost_list


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    pass_dict = {}
    for i in range(N - 1):
        input_raw = read_func().strip().split()
        [a, b, c] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
        if a not in pass_dict:
            pass_dict[a] = []
        pass_dict[a].append((b, c))
        if b not in pass_dict:
            pass_dict[b] = []
        pass_dict[b].append((a, c))

    input_raw = read_func().strip().split()
    [Q, K] = [int(input_raw[0]), int(input_raw[1])]

    cost_list = BFS(pass_dict, K)

    for i in range(Q):
        input_raw = read_func().strip().split()
        [x, y] = [int(input_raw[0]), int(input_raw[1])]
        print cost_list[x] + cost_list[y]


if __name__ == '__main__':
    main()

Solution (Python):
import sys;sys.setrecursionlimit(6**8);I=lambda:map(int,input().split());n,=I();G=[[]for i in[0]*-~n]
for i in[0]*~-n:a,b,c=I();G[a]+=(b,c),;G[b]+=(a,c),
q,k=I()
def f(v,p,u):
 for t,c in G[v]:p==t or f(t,v,u+c)
 G[v]=u
f(k,0,0)
for p in[0]*q:x,y=I();print(G[x]+G[y])

Solution (Python):

import collections
import sys
sys.setrecursionlimit(int(1e7))

def dfs(n, pre, T, dist, d) :
	dist[n] = d
	for i in T[n] :
		if i[0] != pre :
			dfs(i[0], n, T, dist, d + i[1])


N = int(input())
T = collections.defaultdict(lambda : [])
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 = {}
dfs(K, -1, T, d, 0)

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

Solution (Python):
n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

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

dists = {}
def build(x, d=0):
    ss = [(x, 0)]
    while ss:
        x, d = ss.pop()
        if x not in dists:
            dists[x] = d
            for c in edges.get(x, []):
                ss.append((c, d + lens[(min(x,c), max(x,c))]))

build(k)

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

Solution (Python):

import sys
 
def main():
	n = int(input())
	vers = [list(map(int, input().split())) for _ in range(n - 1)]
	q, k = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for _ in range(q)]
 
	
	
 
	new_vers = mapping(n, vers)
	dist = calcMinDist(n, new_vers, k, queries)
	calcQueries(dist, queries, k)
	
def mapping(n, vers):
	new_vers = {i :[] for i in range(n)}
	for ver in vers:
		new_vers[ver[0] - 1].append((ver[1], ver[2]))
		new_vers[ver[1] - 1].append((ver[0], ver[2]))
	return new_vers
 
def calcMinDist(n, new_vers, k, queries):
	dist = [- 1 for _ in range(n)]
	flag = [False for _ in range(n)]
	dist[k - 1] = 0
	flag[k - 1] = True
	dfs(new_vers, dist, flag, k)
	return dist
 
def dfs(new_vers, dist, flag, frm):
	flag[frm - 1] = True
	vs = new_vers[frm - 1]
	for v in vs:
		if flag[v[0] - 1] == False:
			dist[v[0] - 1] = dist[frm - 1] + v[1]
			new_ver, dist, flag, _ = dfs(new_vers, dist, flag, v[0])
 
	return [new_vers, dist, flag, frm]
 
def calcQuery(dist, query, k):
	print(dist[query[0] - 1] + dist[query[1] - 1])
 
def calcQueries(dist, queries, k):
	for query in queries:
		calcQuery(dist, query, k)
 
if __name__ == '__main__':
	sys.setrecursionlimit(1000000)
	main()

Solution (Python):
from collections import deque

INF=float('inf')

n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

q,k=map(int,input().split())
ds=[INF]*n
que=deque([(k-1,0)])
while len(que):
    u,d=que.popleft()
    if ds[u]!=INF:
        continue
    ds[u]=d
    for v,w in g[u]:
        que.append((v,d+w))

for _ in range(q):
    u,v=map(int,input().split())
    print(ds[u-1]+ds[v-1])

Solution (Python):
from collections import deque

INF=float('inf')

n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

q,k=map(int,input().split())
ds=[INF]*n
ds[k-1]=0
que=deque()
que.append((k-1,0))
while len(que):
    u,d=que.popleft()
    for v,w in g[u]:
        if ds[v]==INF:
            ds[v]=d+w
            que.append((v,d+w))

for _ in range(q):
    u,v=map(int,input().split())
    print(ds[u-1]+ds[v-1])

Solution (Python):


import heapq
import sys


INF = sys.maxsize


def dijkstra(num_vertices, adj_list, source=0):
    dist = [INF for _ in range(num_vertices)]
    dist[source] = 0
    pq = [(dist[u], u) for u in range(num_vertices)]
    heapq.heapify(pq)
    while pq:
        _, u = heapq.heappop(pq)
        for v, cost in adj_list[u]:
            new_length = dist[u] + cost
            if new_length < dist[v]:
                dist[v] = new_length
                heapq.heappush(pq, (new_length, v))
    return dist


def main():
    n = int(input())
    adj_list = [set() for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = (int(z) for z in input().split())
        a -= 1
        b -= 1
        adj_list[a].add((b, c))
        adj_list[b].add((a, c))
    q, k = (int(z) for z in input().split())
    k -= 1
    dist = dijkstra(n, adj_list, k)
    for _ in range(q):
        x, y = (int(z) - 1 for z in input().split())
        res = dist[x] + dist[y]
        print(res)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
g = []
d = [0] * (n + 1)
for i in range(n + 1):
    g.append([]);
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])
q, k = map(int, input().split())
def bfs(u):
    s = []
    s.append(u)
    while s:
        v = s[-1]
        s.pop()
        for go in g[v]:
            if not d[go[0]] and go[0] != u:
                d[go[0]] = d[v] + go[1]
                s.append(go[0])
bfs(k)
while q > 0:
    u, v = map(int, input().split())
    print(d[u] + d[v])
    q -= 1

Solution (Python):
n = int(input())
g = []
d = [0] * (n + 1)
for i in range(n + 1):
    g.append([]);
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])
q, k = map(int, input().split())
def bfs(u):
    s = []
    s.append(u)
    while s:
        v = s[-1]
        s.pop()
        for go in g[v]:
            if not d[go[0]] and go[0] != u:
                d[go[0]] = d[v] + go[1]
                s.append(go[0])
bfs(k)
while q > 0:
    u, v = map(int, input().split())
    print(d[u] + d[v])
    q -= 1

Solution (Python):
from queue import Queue

INF=float('inf')

n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

q,k=map(int,input().split())
ds=[INF]*n
ds[k-1]=0
que=Queue()
que.put((k-1,0))
while not que.empty():
    u,d=que.get()
    for v,w in g[u]:
        if ds[v]==INF:
            ds[v]=d+w
            que.put((v,d+w))

for _ in range(q):
    u,v=map(int,input().split())
    print(ds[u-1]+ds[v-1])

Solution (Python):
n = int(input())
edge = [list(map(int, input().split())) for i in range(n-1)]
q, k = map(int, input().split())
query = [list(map(int, input().split())) for i in range(q)]

d = [0 for i in range(n+1)]
visited = [False for i in range(n+1)]
adj = [[] for i in range(n+1)]

for e in edge:
    adj[e[0]].append([e[1], e[2]])
    adj[e[1]].append([e[0], e[2]])
    
st = [k]
visited[k] = True
while st:
    u = st.pop()
    for p in adj[u]:
        v, w = map(int, p)
        if not visited[v]:
            visited[v] = True
            d[v] = d[u]+w
            st.append(v)

for p in query:
    print(d[p[0]]+d[p[1]])

Solution (Python):
from collections import deque

n = int(input())
gr = { i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    gr[a].append((b, c))
    gr[b].append((a, c))
q, k = map(int, input().split())
dmax = 10**14 + 1
dist = [dmax for _ in range(n + 1)]
dist[k] = 0
ls = deque([k])
while 0 < len(ls):
    u = ls.popleft()
    for v, c in gr[u]:
        if dist[v] == dmax:
            dist[v] = dist[u] + c
            ls.append(v)

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

Solution (Python):

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          
        
        dist = {k:float('inf') for k in self.nodes}
        

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    

        return dist

    def prim(self):

        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(self.adj[X[0]][u],X[0],u))

        total_cost=0
        used={n:False for n in nodes}
        used[X[0]]=True
        while True:
            
            
            cost,u,v=heapq.heappop(unused)
            if used[v]:
                continue
            X.append(v)
            used[v]=True
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                if used[u]:
                    continue
                heapq.heappush(unused,(self.adj[u][v],v,u))

        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for u in self.adj:
            for v in self.adj[u]:

                
                G.add_edge(u,v,weight=self.adj[u][v])
                

        pos=nx.spring_layout(G)
        
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        
        
        plt.show()



def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":

    N=int(input())

    g=myGraph()


    for i in range(N-1):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break
        g.add_edge((ss[0],ss[1]),ss[2])
        

    Q,K=spaceinput()

    res=g.dijkstra(K)
    xx=[]
    for k in range(Q):
        xx.append(spaceinput())



    for x,y in xx:
        print(int(res[x]+res[y]))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in[0]*-~n]
for I in[lambda:map(int,input().split())]*~-n:a,b,c=I();G[a]+=(b,c),;G[b]+=(a,c),
q,k=I()
d=[0]*-~n
def f(v,p,u):
 d[v]=u
 for t,c in G[v]:p==t or f(t,v,u+c)
f(k,0,0)
for p in[print]*q:
 x,y=I()
 p(d[x]+d[y])

Solution (Python):
n=int(input())
e=[[] for i in range(n+1)]
for i in range(n-1):
 [a,b,c]=[int(j) for j in input().split()]
 e[a].append([b,c])
 e[b].append([a,c])
[q,k]=[int(j) for j in input().split()]
xy=[]
for i in range(q):
 xy.append([int(j) for j in input().split()])
def dfs(v,n):
    s=[]
    d=[-1 for i in range(n+1)]
    d[v]=0
    s.append(v)
    while len(s):
        v=s.pop()
        
        for i in e[v]:
            if d[i[0]]<0:
                d[i[0]]=d[v]+i[1]
                s.append(i[0])
    return d
d=dfs(k,n)
for i in range(q):
 print(d[xy[i][0]]+d[xy[i][1]])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in[0]*-~n]
for i in[0]*~-n:
    a,b,c=map(int,input().split())
    G[a]+=(b,c),
    G[b]+=(a,c),
q,k=map(int,input().split())
d=[0]*-~n
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[0]*q:
    x,y=map(int,input().split())
    print(d[x]+d[y])

Solution (Python):
from collections import deque

n = int(input())
gr = { i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    gr[a].append((b, c))
    gr[b].append((a, c))
q, k = map(int, input().split())
dmax = 10**14 + 1
dist = [dmax for _ in range(n + 1)]
dist[k] = 0
ls = deque([k])
while 0 < len(ls):
    u = ls[0]
    for v, c in gr[u]:
        if dist[v] == dmax:
            dist[v] = dist[u] + c
            ls.append(v)
    ls.popleft()

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

Solution (Python):
from queue import deque

n = int(input())
edges = [set() for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    edges[a].add((c, b))
    edges[b].add((c, a))
q, k = map(int, input().split())
stack = deque([(0, k)])
costs = [0] * (n + 1)
visited = set()
while stack:
    c, p = stack.popleft()
    costs[p] = c
    visited.add(p)
    stack.extend((c + c2, p2) for c2, p2 in edges[p] if p2 not in visited)

ans = []
for _ in range(q):
    x, y = map(int, input().split())
    ans.append(costs[x] + costs[y])
print('\n'.join(map(str, ans)))

Solution (Python):
from collections import defaultdict

N = int(input())
E = defaultdict(list)
W = dict()

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

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

costs = [float('inf')]*(N+1)
costs[K] = 0

stack = [K]

while stack:
  s = stack.pop()
  for t in E[s]:
    if costs[t] > costs[s] + W[(s,t)]:
      costs[t] = costs[s] + W[(s,t)]
      stack.append(t)

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

Solution (Python):

from collections import defaultdict

INF = 10 ** 20
def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    edges = defaultdict(list)
    for __ in range(N - 1):
        a, b, c = ILI()
        edges[a - 1].append((a - 1, b - 1, c)) 
        edges[b - 1].append((b - 1, a - 1, c))
    Q, K = ILI()
    query = [ILI() for __ in range(Q)]
    return N, edges, Q, K, query


def solve(N, edges, Q, K, query):
    K -= 1
    weight_from_k = [None] * N
    weight_from_k[K] = 0
    used = [False] * N
    used[K] = True
    queue = edges[K]
    while len(queue) != 0:
        next_queue = []
        for fro, to, weight in queue:
            if used[to]:
                continue
            weight_from_k[to] = weight_from_k[fro] + weight
            used[to] = True
            for e in edges[to]:
                next_queue.append(e)
        queue = next_queue

    ans = []
    for x, y in query:
        ans.append(weight_from_k[x - 1] + weight_from_k[y - 1])

    ans = "\n".join(map(str, ans))
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

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

def dfs(now, par, d, dist, g):
    dist[now] = d
    for to, cost in g[now]:
        if to == par: continue
        dfs(to, now, d + cost, dist, g)


n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b, c = map(int, raw_input().split())
    a -= 1; b -= 1
    g[a].append([b, c])
    g[b].append([a, c])
q, k = map(int, raw_input().split())
k -= 1
dist = [-1] * n
dfs(k, -1, 0, dist, g)
for i in xrange(q):
    x, y = map(int, raw_input().split())
    x -= 1; y -= 1
    print dist[x] + dist[y]

Solution (Python):
import sys  
sys.setrecursionlimit(200000)
n=int(raw_input())
tr=[[] for i in range(n)]
for i in range(n-1) :
  a,b,c=map(int,raw_input().split())
  a -= 1
  b -= 1
  tr[a].append((b,c))
  tr[b].append((a,c))
m,k=map(int,raw_input().split())
k -= 1
dis=[0 for i in range(n)]
def dfs(u,w=-1,l=0) :
  dis[u]=l
  for v,v1 in tr[u] :
    if v!=w :
      dfs(v,u,l+v1)
dfs(k)
for i in range(m) :
  x,y=map(int,raw_input().split())
  x-=1
  y-=1
  print dis[x]+dis[y]

Solution (Python):

from collections import defaultdict, deque


def bfs(graph, n, start):
    q = deque([start])

    dists = [-1] * (n+1)
    dists[start] = 0

    while q:
        cur = q.pop()

        for neigh, d in graph[cur].items():
            if dists[neigh] == -1:
                q.appendleft(neigh)
                dists[neigh] = dists[cur] + d

    return dists


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

    graph = defaultdict(dict)

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

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

    dists = bfs(graph, n, k)

    for _ in range(q):
        start, end = (int(x) for x in input().split())
        print(dists[start] + dists[end])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000001)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

for i in range(n-1):
    a, b, c = na()
    g[a].append((b,c))
    g[b].append((a,c))

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
dfs(k, -1, g, par, dw, 0)

for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

for i in range(n-1):
    a, b, c = na()
    g[a].append((b,c))
    g[b].append((a,c))

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
from queue import Queue
qs = Queue()
qs.put(k)
dw[k] = 0

while not qs.empty():
    cur = qs.get()
    for e in g[cur]:
        if e[0] != par[cur]:
            par[e[0]] = cur
            dw[e[0]] = dw[cur] + e[1]
            qs.put(e[0])




for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])

Solution (Python):
import heapq

def dijkstra(s,g,n):
    d=[float('inf')]*n
    d[s]=0
    pq=[]
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v,c in g[u]:
            if d[u]+c<d[v]:
                d[v]=d[u]+c
                heapq.heappush(pq,[d[v],v])
    return d

n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b, c = map(int, raw_input().split())
    a -= 1; b -= 1
    g[a].append([b, c])
    g[b].append([a, c])
q, k = map(int, raw_input().split())
k -= 1
dist = dijkstra(k, g, n)
for i in xrange(q):
    x, y = map(int, raw_input().split())
    x -= 1; y -= 1
    print dist[x] + dist[y]

Solution (Python):
from heapq import heappush, heappop
n = int(input())
G = [[] for i in range(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())

dist = [10**18]*n
que = [(0, k-1)]
dist[k-1] = 0
while que:
    cost, v = heappop(que)
    if dist[v] < cost:
        continue
    for t, c in G[v]:
        if cost + c < dist[t]:
            dist[t] = cost + c
            heappush(que, (cost + c, t))
ans = []
for i in range(q):
    x, y = map(int, input().split())
    ans.append("%d" % (dist[x-1] + dist[y-1]))
print("\n".join(ans))

Solution (Python):
from sys import stdin
input = stdin.readline
n = int(input())
adj = [[] for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    adj[a].append((b,c))
    adj[b].append((a,c))
qn, k = map(int,input().split())

from collections import deque
dist = [-1]*(n+1)
dist[k] = 0
Q = deque()
Q.append(k)
while len(Q):
    p = Q.popleft()
    for q,c in adj[p]:
        if dist[q] != -1: continue
        dist[q] = dist[p]+c
        Q.append(q)
for i in range(qn):
    x, y = map(int,input().split())
    print(dist[x]+dist[y])