Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import math
N=int(input())
tree=[[0]*N for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split(' '))
    tree[a-1][b-1] = c
    tree[b-1][a-1] = c
tree = np.array(tree)
Q,K=map(int,input().split(' '))
csr = csr_matrix(tree)
ans = dijkstra(csr,indices=K-1)
for i in range(Q):
    s,e=map(int,input().split(' '))
    print(int(ans[s-1]+ans[e-1]))

### FIXED CODE ###

from collections import deque

N = int(input())
ABC=[map(int,input().split(' ')) for i in range(N-1)]
Q,K =  map(int,input().split(' '))
query = [map(int,input().split(' ')) for i in range(Q)]
tree = [[] for i in range(N+1)]
for a,b,c in ABC:
    tree[b].append((a,c))
    tree[a].append((b,c))
k_shortest = [0]*(N+1)
stack=deque([K])
while stack:
    k = stack.popleft()
    for v,d in tree[k]:
        if k_shortest[v] == 0:
            k_shortest[v] = k_shortest[k]+d
            stack.append(v)
for i,j in query:
    print(k_shortest[i]+k_shortest[j])
### BUGGY CODE ###

x = int(input())
N = len(str(x))
L = []
while N != 0: 
    L.append( x % 10 )
    N -= 1
    x = x // 10
if sum(L) % 9 == 0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

x = int(input())
N = str(x)
array = list(map(int, N))
if sum(array) % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n,m,*t=map(int,open(0).read().split())
d=[0,0]+[1e18]*n
for l,r,c in sorted(zip(*[iter(t)]*3)):
 for i in range(r,l,-1):
  if d[l]+c<d[i]:d[i]=d[l]+c
  else:break
print(-(d[-2]>1e17)or d[-2])

### FIXED CODE ###

from heapq import*
n,_,*t=map(int,open(0).read().split())
e=[[]for _ in'_'*n]
for l,r,c in zip(*[iter(t)]*3):e[l-1]+=(c,r-1),
for i in range(n-1):e[i+1]+=(0,i),
d=[0]+[1e18]*n
q=[(0,0)]
while q:
  c,v=heappop(q)
  for b,w in e[v]:
    if b+c<d[w]:
      d[w]=b+c
      heappush(q,(b+c,w))
print(-(d[-2]>1e17)or d[-2])
### BUGGY CODE ###

import sys
X,K,D= map(int,input().split())
temp = X

if abs(X) > K*D:
    print(abs(X)-K*D)
    sys.exit()
    
for t in range(K):
    # 絶対値の小さい方に移動
    if abs(temp - D) < abs(temp + D):
        temp = temp-D
    else:
        temp = temp+D

    # 移動幅より小さくなったとき
    if abs(temp) < D:
        if (K-t-1) % 2 == 0:
            print(abs(temp))
            sys.exit()
        else:
            if abs(temp - D) < abs(temp + D):
                temp = temp-D
                print(abs(temp))
                sys.exit()
            else:
                temp = temp+D
                print(abs(temp))
                sys.exit()

print(abs(temp))



### FIXED CODE ###

import sys
X,K,D= map(int,input().split())
temp = X

if abs(X) > K*D:
    print(abs(X)-K*D)
    sys.exit()
    
for t in range(K):
    # 絶対値の小さい方に移動
    if abs(temp - D) < abs(temp + D):
        temp = temp-D
    else:
        temp = temp+D

    # 移動幅より小さくなったとき
    if abs(temp) < D:
        if (K-t-1) % 2 == 0:
            print(abs(temp))
            sys.exit()
        else:
            if abs(temp - D) < abs(temp + D):
                temp = temp-D
                print(abs(temp))
                sys.exit()
            else:
                temp = temp+D
                print(abs(temp))
                sys.exit()

print(abs(temp))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 7 + 10**9
A = []
leng = len(format(max(a), 'b'))
bit_acc = [0 for i in range(leng)]
for i in range(n):
    A.append(list(map(int, format(a[i], 'b').zfill(leng))))
for i in range(leng):
    bit_acc[i] = sum([A[j][i] for j in range(n)]) 
ans = 0
for i in range(n):
    for j in range(leng):
        if A[i][j] == 1:
            ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
        else:
            ans += bit_acc[j] * (2 ** (leng - j - 1))
print((ans * 500000004) % mod)



### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import heapq, copy
N = int(input())
A = [int(i) for i in input().split()]
Aleft = copy.deepcopy(A[:N])
heapq.heapify(Aleft)
Aright = copy.deepcopy(A[N:])
ArightS = sorted(copy.deepcopy(A[N:]))
score = sum(A[:N]) - sum(ArightS[:N])

for i in range(1, N+1):
    a = Aright.pop(0)
    ArightS.remove(a)
    heapq.heappush(Aleft, a)
    heapq.heappop(Aleft)
    score = max(score, sum(Aleft) - sum(ArightS[:N]))

print(score)

### FIXED CODE ###

import heapq
N = int(input())
A = [int(i) for i in input().split()]

sumLeft = [0] * (N+1) #A[:N+i]中のN要素の和の最大値のリスト
sumLeft[0] = sum(A[:N])
Aleft = A[:N]
heapq.heapify(Aleft)

sumRight = [0] * (N+1) #A[N+i:]中のN要素の和の最小値のリスト
sumRight[-1] = sum(A[2*N:]) 
Aright = [-1*i for i in A[2*N:]] #最大値をpopするために要素を-1倍しておく
heapq.heapify(Aright)

for i in range(1, N+1):
    a = A[N+i-1]
    b = -1 * A[2*N-i]
    sumLeft[i] = sumLeft[i-1] + a - heapq.heappushpop(Aleft, a)
    sumRight[-1-i] = sumRight[-i] + heapq.heappushpop(Aright, b) - b

score = sumLeft[0] - sumRight[0]
for i in range(1, N+1):
    score = max(score, sumLeft[i] - sumRight[i])
print(score)
### BUGGY CODE ###

import copy

N, K = map(int, input().split())
A = list(map(int, input().split()))

for k in range(K):
  B = [0] * N
  for i in range(N):
    s = i - A[i]
    if s < 0:
      s = 0
    l = i + A[i] + 1
    if l >= N:
      l = N
    for j in range(s, l):
      B[j] += 1
  A = B
    
for b in B:
  print(b, end=" ")

### FIXED CODE ###

from numba import jit

@jit
def solve(N, K, A):
  for k in range(K):
    B = [0] * N
    for i in range(N):
      l = max(0, i - A[i])
      r = i + A[i] + 1
      B[l] += 1
      if r < N:
        B[r] -= 1

    for j in range(N - 1):
      B[j + 1] += B[j]
  
    if A == B:
      return B
    A = B
  return B
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = solve(N, K, A)
for b in B:
  print(b, end=" ")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
x = []
for i in range(1,n):
    x.append(abs(sum(a[:i])-sum(a[i:])))
print(min(x))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = float("INF")
X = sum(a)

x = 0
for i in range(n):
    x += a[i]
    if i+1 < n:
        ans = min(ans,abs(X-2*x))
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
Field = []
Field.append(['#'] * (W+2))
for _ in range(H):
    Field.append((list('#'+input()+'#')))
Field.append(['#'] * (W+2))

DPL = [[0 for _ in range(W+2)] for _ in range(H+2)]
DPR = [[0 for _ in range(W+2)] for _ in range(H+2)]
DPU = [[0 for _ in range(W+2)] for _ in range(H+2)]
DPD = [[0 for _ in range(W+2)] for _ in range(H+2)]

for h in range(1, H+1):
    for w in range(1, W+1):
        if Field[h][w] == '#':
            DPL[h][w] = 0
        else:
            DPL[h][w] = DPL[h][w-1] + 1
for h in range(1, H+1):
    for w in range(1, W+1):
        if Field[h][W-w+1] == '#':
            DPR[h][W-w+1] = 0
        else:
            DPR[h][W-w+1] = DPR[h][W-w+1+1] + 1
for h in range(1, H+1):
    for w in range(1, W+1):
        if Field[h][w] == '#':
            DPU[h][w] = 0
        else:
            DPU[h][w] = DPU[h-1][w] + 1   
for h in range(1, H+1):
    for w in range(1, W+1):
        if Field[H-h+1][w] == '#':
            DPD[H-h+1][w] = 0
        else:
            DPD[H-h+1][w] = DPD[H-h+1+1][w] + 1 
ans = 0          
for h in range(1, H+1):
    for w in range(1, W+1):
        ans = max(ans,DPL[h][w]+DPR[h][w]+DPU[h][w]+DPD[h][w])
print(ans-3)

### FIXED CODE ###

H, W = map(int, input().split())
Field = []
Field.append(['#'] * (W+2))
for _ in range(H):
    Field.append((list('#'+input()+'#')))
Field.append(['#'] * (W+2))

DPL = [[0 for _ in range(W+2)] for _ in range(H+2)]
DPR = [[0 for _ in range(W+2)] for _ in range(H+2)]
DPU = [[0 for _ in range(W+2)] for _ in range(H+2)]
DPD = [[0 for _ in range(W+2)] for _ in range(H+2)]

for h in range(1, H+1):
    for w in range(1, W+1):
        if Field[h][w] == '#':
            DPL[h][w] = 0
        else:
            DPL[h][w] = DPL[h][w-1] + 1
for h in range(1, H+1):
    for w in range(1, W+1):
        if Field[h][W-w+1] == '#':
            DPR[h][W-w+1] = 0
        else:
            DPR[h][W-w+1] = DPR[h][W-w+1+1] + 1
for h in range(1, H+1):
    for w in range(1, W+1):
        if Field[h][w] == '#':
            DPU[h][w] = 0
        else:
            DPU[h][w] = DPU[h-1][w] + 1   
for h in range(1, H+1):
    for w in range(1, W+1):
        if Field[H-h+1][w] == '#':
            DPD[H-h+1][w] = 0
        else:
            DPD[H-h+1][w] = DPD[H-h+1+1][w] + 1 
ans = 0          
for h in range(1, H+1):
    for w in range(1, W+1):
        ans = max(ans,DPL[h][w]+DPR[h][w]+DPU[h][w]+DPD[h][w])
print(ans-3)
### BUGGY CODE ###

from bisect import bisect_right

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0

for i in range(N):
	a = bisect_right(B, A[i])
	for j in range(a, N):
		b = bisect_right(C, B[j])
		ans += (N - b)

print(ans)


### FIXED CODE ###

from bisect import bisect_right, bisect_left

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0

for bi in range(N):
    ai_max = bisect_left(A, B[bi])
    ci_min = bisect_right(C, B[bi])
    ans += (ai_max) * (N - ci_min)

print(ans)
### BUGGY CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

N, Ma, Mb = map(int, input().split())

a = [0] * N
b = [0] * N
c = [0] * N

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

ans = float('inf')
for i in range(1 << N):
    tmp_a = 0
    tmp_b = 0
    tmp_c = 0
    for j in range(N):
        if ((i >> j) & 1) == 1:
            tmp_a += a[j]
            tmp_b += b[j]
            tmp_c += c[j]
    if tmp_a == 0 or tmp_b == 0:
        continue
    gcd_ab = gcd(tmp_a, tmp_b)
    if tmp_a / gcd_ab == Ma and tmp_b / gcd_ab == Mb:
        if ans > tmp_c:
            ans = tmp_c

if ans == float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N , Ma, Mb = map(int, input().split())

a = [0] * N
b = [0] * N
c = [0] * N

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

# TLEになってしまうためinfを5000とかで設定する
INF = 5000

# 最小値を求める問題なのでinfで初期化
# dp[i][sun_a][sum_b]で考えていく
dp = [[[INF for _ in range(10 * N + 1)] for _ in range(10 * N + 1)] for _ in range(N+1)]

# 初期選択状態を0とする

dp[0][0][0] = 0
for i in range(N):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if dp[i][j][k] == INF:
                continue
            
            # 選ばなかった場合
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            # 選んだ場合
            dp[i+1][j+a[i]][k+b[i]] = min(dp[i+1][j+a[i]][k+b[i]], dp[i][j][k] + c[i])


ans = INF
# 0スタートは何を選んでいない状態となり最小値が0になってしまうため1から開始する

# TLEになったため変更
#for i in range(1,10 * N + 1):
#    for j in range(1,10 * N + 1):
#        if i * Mb != j * Ma:
#            continue
#        ans = min(ans, dp[N][i][j])
#

for i in range(1, 10*N+1):
        if i*Ma>10*N or i*Mb>10*N:
            break
        ans = min(ans, dp[N][i*Ma][i*Mb])

if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def resolve():
    N, X, Y = map(int, input().split())
    graph = np.zeros((N + 1, N + 1), dtype=np.int64)

    for i in range(1, N):
        graph[i, i+1] += 1
        graph[i+1, i] += 1
    graph[X, Y] = 1
    graph[Y, X] = 1

    dist = dijkstra(csgraph=csr_matrix(graph)).astype(np.int64)
    dist_U = np.triu(dist[1:, 1:])
    ans = []
    for i in range(1, N):
        cnt = sum(np.where(dist_U==i))
        ans.append(len(cnt))

    for a in ans:
        print(a)
        
if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


def resolve():
    N, X, Y = map(int, input().split())
    graph = np.zeros((N + 1, N + 1), dtype=np.int64)

    for i in range(1, N):
        graph[i, i + 1] += 1
        graph[i + 1, i] += 1
    graph[X, Y] = 1
    graph[Y, X] = 1

    dist = dijkstra(csgraph=csr_matrix(graph)).astype(np.int64)
    ans = np.bincount(dist[1:, 1:].ravel(), minlength=N) // 2
    return print(*ans[1:], sep='\n')


if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

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

c = [0]*N
res = [0]*N
for p,x in PX:
    c[p-1] += x

def BFS(start,edges,N,c):
    roots=[[] for _ in range(N)]
    for a,b in edges:
        roots[a-1]+=[(b-1,c[b-1])]
        roots[b-1]+=[(a-1,0)]
    queue=[]
    visited=[start]
    queue.append(start)
    res[start] = c[start]
    while queue:
        label = queue.pop()
        for i,c in roots[label]:
            if i not in visited:
                res[i]= res[label]+c
                queue += [i]
                visited.append(i)
    return res
print(*BFS(0,edges,N,c))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

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

c = [0]*N
res = [-1]*N
for p,x in PX:
    c[p-1] += x

def BFS(start,edges,N,c):
    roots=[[] for _ in range(N)]
    for a,b in edges:
        roots[a-1]+=[(b-1,c[b-1])]
    queue=[]
    queue.append(start)
    res[start] = c[start]
    while queue:
        label = queue.pop()
        for i,c in roots[label]:
            if res[i] == -1:
                res[i]= res[label]+c
                queue += [i]
    return res
print(*BFS(0,edges,N,c))
### BUGGY CODE ###

N, K = map(int,input().split())
h = [int(i) for i in input().split()]

# DPテーブルを初期化
dp = [float("inf")]*N

# 初期状態
dp[0] = 0

# 足場iから足場(i+j)にジャンプする
for i in range(0,N):
    for j in range(1,K+1):
        if (i+j) >= N:
            break
        dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))

print(dp[-1])


### FIXED CODE ###

N, K = map(int,input().split())
h = [int(i) for i in input().split()]

# DPテーブルを初期化
dp = [float("inf")]*N

# 初期状態
dp[0] = 0

# 足場iから足場(i+j)にジャンプする
for i in range(0,N):
    for j in range(1,K+1):
        if (i+j) >= N:
            break
        dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))

print(dp[-1])
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    query = list(map(str, input().split()))
    if query[0]=='1':
        S = ''.join(reversed(list(S)))
    else:
        if query[1]=='1':
            S = query[2] + S
        else:
            S = S + query[2]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())
hanten = 1
front = []
back = []
for _ in range(Q):
    q = list(map(str, input().split()))
    if q[0]=='1':
        hanten *= -1
    else:
        if hanten==1:
            if q[1]=='1':
                front.append(q[2])
            else:
                back.append(q[2])
        else:
            if q[1]=='1':
                back.append(q[2])
            else:
                front.append(q[2])


if hanten==1:
    print(''.join(list(reversed(front)) + list(S) + back))
else:
    print(''.join(list(reversed(list(S)+back))+front))
### BUGGY CODE ###

import sys


def resolve():
    readline = sys.stdin.readline    # 1行だけ文字列にする

    N, K = map(int, readline().split())
    h = [int(x) for x in readline().split()]

    inf = float('inf')
    dp = [inf] * N
    dp[0] = 0

    for i in range(1, N):
        if i < K:
            for j in range(i + 1):
                dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
        else:
            for j in range(K + 1):
                dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
    print(dp[N - 1])
            

resolve()


### FIXED CODE ###

def resolve():
    import sys
    
    readline = sys.stdin.readline

    N, K = map(int, readline().split())
    h = [int(x) for x in readline().split()]

    inf = float('inf')
    dp = [inf] * N
    dp[0] = 0

    for i in range(1, N):
        leng = i + 1 if i < K else K + 1
        for j in range(leng):
            cal = dp[i - j] + abs(h[i] - h[i - j])
            if dp[i] > cal:
                dp[i] = cal

    print(dp[-1])
            

resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

AB=[]
for a in A:
    for b in B:
        AB.append(a+b)

C.sort(reverse=True)
AB.sort(reverse=True)


ABX=[AB[0]-ab for ab in AB]
CX=[C[0]-c for c in C]

ABX.append(float("inf"))
CX.append(float("inf"))

j=0
for i in range(X*Y):
    while j<Z-1 and CX[j]<ABX[i]:
        j+=1

    if (i+1)*(j+1)>K:
        break

#print(i,j)

MIN=AB[i]+C[j]
MAX=AB[0]+C[0]-MIN
LIST=[]

for ii in range(X*Y):
    if AB[0]-AB[ii]>MAX:
        break
    for jj in range(Z):
        if AB[ii]+C[jj]>=MIN:
            LIST.append(AB[ii]+C[jj])
        else:
            break

LIST.sort(reverse=True)

for j in range(K):
    print(LIST[j])

### FIXED CODE ###

import sys
input = sys.stdin.readline

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

AB=[]
for a in A:
    for b in B:
        AB.append(a+b)

AB.sort(reverse=True)
AB=AB[:K]

ALL=[]

for ab in AB:
    for c in C:
        ALL.append(ab+c)

ALL.sort(reverse=True)

for k in range(K):
    print(ALL[k])
### BUGGY CODE ###

import bisect

n = int(input())

d = {}
m = 1
for i in range(n):
    s = input()
    d.setdefault(s, 0)
    d[s] += 1
    if m < d[s]:
        m = d[s]

l = []
for i, j in d.items():
    if j == m:
        bisect.insort_left(l, i)
        
for i in l:
    print(i)


### FIXED CODE ###

from collections import Counter

n = int(input())

l = [input() for i in range(n)]

c = Counter(l)

ml = c.most_common()
mc = ml[0][1]

ml.sort()

for i in ml:
    if i[1] == mc:
        print(i[0])
### BUGGY CODE ###

#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, depth_first_tree

#sys.setrecursionlimit(10000)

N = int(input())

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

for _ in range(N-1):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)

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

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1 = dijkstra(graph, indices = K-1, directed=False)

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


### FIXED CODE ###

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        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 間のコスト
    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)

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

import sys
f = sys.stdin

s,n,m = map(int, f.readline().split())
x = list(map(int, f.readline().split()))
tp = [list(map(int, line.split())) for line in f]

c = [ti - x[pi - 1] for ti, pi in tp]
c.sort()
min_c = c[0]
c = [ci - min_c for ci in c]
d = c[:]
for i in range(1,len(d)):
    d[i] += d[i - 1]

w = [[0 for j in range(n)] for i in range(n)]
for j in range(1, n):
    for i in range(j):
        w[i][j] = c[j] * (j - i + 1) - (d[j] - d[i] + c[i])

def calc(dp,w):
    ret = [99999999] * len(dp)
    ret[0] = 0

    for j in range(1,len(dp)):
        for i in range(j):
            ret[j] = min(ret[j], dp[i] + w[i+1][j]) # ????°????
    
    return ret

dp = w[0][:]
for bus in range(1,m):
    dp = calc(dp,w)
        
print(dp[-1])

### FIXED CODE ###

from operator import itemgetter
#@profile
def calc(w,pdp,pl,pr,dp,l,r):
    if l >= r:
        return
    m = (l + r) // 2
    dp[m], i = min([(pdp[i] + w[i+1][m],i) for i in range(pl,min(m,pr))], key=itemgetter(0))
    calc(w,pdp,pl,i+1,dp,l,m)
    calc(w,pdp,i,pr,dp,m+1,r)
    return dp

import sys
f = sys.stdin

s,n,m = map(int, f.readline().split())
x = list(map(int, f.readline().split()))
tp = [list(map(int, line.split())) for line in f]

c = [ti - x[pi - 1] for ti, pi in tp]
c.sort()
min_c = c[0]
c = [ci - min_c for ci in c]
d = c[:] 
for i in range(1,len(d)):
    d[i] += d[i - 1]

w = [[0 for j in range(n)] for i in range(n)]
for j in range(1, n):
    for i in range(j): 
        w[i][j] = c[j] * (j - i + 1) - (d[j] - d[i] + c[i])

dp = w[0][:]
for bus in range(2,m + 1):
    pdp = dp 
    dp = [0] * len(pdp)
    pl = bus - 2
    pr = n-m+bus
    if pl > pr:
        continue
    dp = calc(w,pdp,pl,pr,dp,bus,n)
        
print(dp[-1])
### BUGGY CODE ###

a,b,k=map(int,input().split())
S=[]
for i in range(a,b+1):
    S.append(i)
T=sorted(list(set(S[:k]+S[-k:])))
for i in T:
    print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
S=[]

for i in range(k):
    if a+i>b:
        break
    S.append(a+i)
    
for i in range(k):
    if b-i<a:
        break
    S.append(b-i)
    
S=sorted(list(set(S)))
for i in S:
    print(i)