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

from itertools import permutations
import heapq

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))

cost = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in cost.keys():
        cost[a] = [(b, c)]
    else:
        cost[a].append((b, c))
    if not b in cost.keys():
        cost[b] = [(a, c)]
    else:
        cost[b].append((a, c))
        
dist = [[INF]*(n+1) for _ in range(n+1)]
for st in range(1, n+1):
    d = [INF]*(n+1)
    d[st] = 0
    path = [(0, st)]
    heapq.heapify(path)
    while len(path) > 0:
        c, node = heapq.heappop(path)
        if d[node] < c:
            continue
        d[node] = c
        for node_next, c_next in cost[node]:
            heapq.heappush(path, (d[node]+c_next, node_next))
    dist[st] = d
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)


### FIXED CODE ###

from itertools import permutations

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c

from scipy.sparse import csgraph
dist = csgraph.floyd_warshall(dist)
# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(int(ans))
### BUGGY CODE ###

A, B = map(int, input().split())
ans = 0
for i in range(60):
    # 含まれる1の数を数える
    tmp = (B-A) // 2**(i+1) * 2**i
    # print(tmp)
    p = A%(2**(i+1))
    q = (B-A)%(2**(i+1))
    # print(p, q)
    for j in range(p, p + q + 1):
        if j % (2**(i+1)) >= 2**i:
            tmp += 1
    # print(tmp)
    ans += (tmp%2) * 2**i
print(ans)

### FIXED CODE ###

A, B = map(int, input().split())
ans = 0
for i in range(40):
    # 含まれる1の数を数える
    tmp = (B-A) // 2**(i+1) * 2**i
    p = A%(2**(i+1))
    q = (B-A)%(2**(i+1))
    # p から p+qの中で余りが2**i ~ 2**(i+1)-1になる個数を求める
    tmp += max(min(p+q,2**(i+1)-1) - max(p,2**i)+1,0)
    tmp += max(min(p+q,2**(i+1)-1 + 2**(i+1)) - max(p,2**i + 2**(i+1))+1,0)
    ans += (tmp%2) * 2**i
print(ans)
### BUGGY CODE ###

broken_step = []
     
line = [int(s) for s in input().split()]
     
N, M = line[0], line[1]
     
for i in range(M):
    step_num = int(input().split()[0])
    broken_step.append(step_num)
        
        
dp = [0]*(N+1)
dp[0] = 1
if 1 in broken_step:
    dp[1] = 0
else:
    dp[1] = 1
     
for i in range(2, N+1):
    dp[i] = (dp[i-1]+dp[i-2])%(10**9 + 7) if i not in broken_step else 0
print(dp[N])

### FIXED CODE ###

MOD = (10**9 + 7)

     
line = [int(s) for s in input().split()]
     
N, M = line[0], line[1]
     
b = [0]*(N+1)
for i in range(M):
    step_num = int(input().split()[0])
    b[step_num] = 1
        
        
dp = [0]*(N+1)
dp[0] = 1
if b[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1
     
for i in range(2, N+1):
    if b[i] == 1:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%MOD
print(dp[N])
### BUGGY CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

def Maze_Master(y, x, c):
    if y < 0 or y > h-1 or x < 0 or x > w-1 or m[y][x] != 0 and m[y][x] < c or s[y][x] == "#":
        pass
    else:
        m[y][x] = c
        c += 1
        Maze_Master(y+1, x, c)
        Maze_Master(y-1, x, c)
        Maze_Master(y, x+1, c)
        Maze_Master(y, x-1, c)
    return m
    
l = []
for y in range(h):
    for x in range(w):
        m = [[0]*w for _ in range(h)]
        ans = Maze_Master(y, x, 1)
        for i in ans:
            for j in i:
                l.append(j)

print(max(l) - 1)

### FIXED CODE ###

import queue

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            t = [["."]*w for _ in range(h)]
            t[i][j] = 0
            q = queue.Queue()
            q.put((j, i))
            while True:
                x, y = q.get()
                for k, l in (1, 0), (-1, 0), (0, 1), (0, -1):
                    if (0 <= x+k and x+k < w and
                        0 <= y+l and y+l < h and
                        s[y+l][x+k] == "." and t[y+l][x+k] == "."):
                            t[y+l][x+k] = t[y][x] + 1
                            q.put((x+k, y+l))
                            
                if q.empty():
                    ans = max(ans, t[y][x])
                    break
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split(" "))
a=[]
ans = 1
for i in range(m):
    a.append(int(input()))
    if a[i]-1 == a[i-1]:
        ans = 0
if ans == 1:
    for j in range(n,-1,-1):
        if j in a:
            ans *= 1
        elif j+1 in a or j+2 in a:
            ans *= 1
        elif j+2 > n:
            ans *= 1
        elif not(j+3 in a) and not(j+3 > n):
            temp = ans
            ans += t
            t = temp
        else:
            t = ans
            ans *= 2

print(ans % 1000000007)


### FIXED CODE ###

n,m = map(int,input().split(" "))
a=[0] * (n+1)
mod = 10 ** 9 + 7
for i in range(m):
    a[int(input())] = 1

dp = [0] * (n+1)
for j in range(n+1):
    if a[j] == 1:
        dp[j] = 0
    elif j == 1 or j == 0:
        dp[j] = 1
    else:
        dp[j] = (dp[j-1] + dp[j-2]) % mod

print(dp[n])
### BUGGY CODE ###

n=int(input())
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())

l = list([n, 0, 0, 0, 0, 0])
count=0
while l[5] < n:
   d_5 = e if l[4] > e else l[4]
   l[5] += d_5
   l[4] -= d_5
   d_4 = d if l[3] > d else l[3]
   l[4] += d_4
   l[3] -= d_4
   d_3 = c if l[2] > c else l[2]
   l[3] += d_3
   l[2] -= d_3
   d_2 = b if l[1] > b else l[1]
   l[2] += d_2
   l[1] -= d_2
   d_1 = a if l[0] > a else l[0]
   l[1] += d_1
   l[0] -= d_1
   count += 1
print(count)



### FIXED CODE ###

import math
n=int(input())
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())

m = min(a, b, c, d, e)
print(math.ceil(n/m) + 4)
### BUGGY CODE ###

mod = 10 ** 9 + 7

K = map(int, iter(input()))
D = int(input())

s = 0
dp = [0] * D
for k in K:
    ndp = [0] * D
    for d in range(10):
        for i, dpi in enumerate(dp):
            ndp[(i + d) % D] += dpi

    for d in range(k):
        ndp[(s + d) % D] += 1

    s = (s + k) % D
    dp = [x % mod for x in ndp]

print((dp[0] - (s != 0)) % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7

K = input()
D = int(input())

s = 0
dp = [0] * D
for k in K:
    k = int(k)

    T = [0] * D
    for i, dpi in enumerate(dp):
        for x in range(10):
            T[(i + x) % D] = (T[(i + x) % D] + dpi) % mod
    for x in range(k):
        T[(s + x) % D] += 1

    s = (s + k) % D
    dp = T

print((dp[0] + (-1 if s != 0 else 0)) % mod)
### BUGGY CODE ###

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

for i in range(N):
    s = A.count(i+1)
    print(s)
    

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = [0 for i in range(N)]

for i in range(N-1):
    S[A[i]-1] += 1

for i in range(N):
    print(S[i])
### BUGGY CODE ###

S = input()
N = len(S)
q = []
A = 13-5
for i in range(N-1,-1,-1):
    if S[i] == '?':
        q.append(N-i-1)
    else:
        A = (A+int(S[i])*(10**(N-i-1)))%13
DP= [[0]*13 for i in range(len(q)+1)]
DP[0][A] = 1
T = [1,10,9,12,3,4]
for i in range(len(q)):
    for j in range(13):
        for k in range(10):
            DP[i+1][(j+k*T[q[i]%6])%13] = (DP[i+1][(j+k*T[q[i]%6])%13]+DP[i][j])%(10**9+7)
print(DP[-1][0])

### FIXED CODE ###

S = input()
N = len(S)
DP =[0]*13
DP[0] = 1
A = 0
MOD = 10**9+7

T = [1,10,9,12,3,4]
A = 0
for i in range(N):
    A*=10
    if S[i] == "?":
        hoge = [0]*13
        for j in range(13):
            for k in range(10):
                hoge[(j+k*T[(N-i-1)%6])%13] = (hoge[(j+k*T[(N-i-1)%6])%13] + DP[j])%MOD
        DP = hoge[:]
    else:
        A += int(S[i])
    A = A%13
print(DP[(5-A)%13])
### BUGGY CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))

mod = 998244353

dp = [[0] * 5000 for _ in range(5000)]

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x % mod

pow2 = [1] * (n + 1)
for i in range(n):
    pow2[i + 1] = pow2[i] * 2 % mod
inv2 = pow_k(2, mod - 2)

dp[0][0] = pow2[n]
for i in range(1, n + 1):
    for j in range(s + 1):
        dp[i][j] = dp[i - 1][j]
        if j >= a[i - 1]:
            dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i - 1]] * inv2 % mod) % mod
print(dp[n][s])


### FIXED CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))

mod = 998244353

dp = [[0] * 4000 for _ in range(4000)]

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x % mod

inv2 = pow_k(2, mod - 2)
pow2n = pow_k(2, n)

dp[0][0] = pow2n
for i in range(1, n + 1):
    for j in range(s + 1):
        if j >= a[i - 1]:
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - a[i - 1]] * inv2 % mod) % mod
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][s])
### BUGGY CODE ###

MOD = 998244353
HALF = (MOD + 1) // 2


def solve(a, b, c, d):
    dp1 = [[0] * (d + 1) for _ in range(c + 1)]
    dp2 = [[0] * (d + 1) for _ in range(c + 1)]
    dp3 = [[0] * (d + 1) for _ in range(c + 1)]
    dp1[a][b] = 1
    dp2[a][b] = 0
    dp3[a][b] = 0
    for i in range(a + 1, c + 1):
        dp1[i][b] = (pow(b - 1, i - a, MOD) + pow(b - 1, i - a - 1, MOD) * 1 * (i - a)) % MOD
        dp3[i][b] = (pow(b, i - a, MOD) - dp1[i][b]) % MOD
    for j in range(b + 1, d + 1):
        dp1[a][j] = (pow(a - 1, j - b, MOD) + pow(a - 1, j - b - 1, MOD) * 1 * (j - b)) % MOD
        dp2[a][j] = (pow(a, j - b, MOD) - dp1[a][j]) % MOD
    for i in range(a + 1, c + 1):
        for j in range(b + 1, d + 1):
            dp1[i][j] = (((dp1[i - 1][j] + dp2[i - 1][j]) * (j - 1) + (dp1[i][j - 1] + dp3[i][j - 1]) * (i - 1)) * HALF) % MOD
            dp2[i][j] = (dp2[i][j - 1] * i + dp1[i][j - 1] + dp3[i][j - 1]) % MOD
            dp3[i][j] = (dp3[i - 1][j] * j + dp1[i - 1][j] + dp2[i - 1][j]) % MOD

    # print(dp1, dp2, dp3)
    # print((dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD)
    return (dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD


def main():
    a, b, c, d = map(int, input().split())
    res = solve(a, b, c, d)
    print(res)


def test():
    assert solve(1, 1, 2, 2) == 3
    assert solve(1, 1, 3, 3) == 30
    assert solve(2, 1, 3, 4) == 65
    assert solve(31, 41, 59, 265) == 387222020


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

MOD = 998244353


def solve(a, b, c, d):
    dp1 = [[0] * (d + 1) for _ in range(c + 1)]
    dp2 = [[0] * (d + 1) for _ in range(c + 1)]
    dp3 = [[0] * (d + 1) for _ in range(c + 1)]
    dp1[a][b] = 1
    dp2[a][b] = 0
    dp3[a][b] = 0
    for i in range(a + 1, c + 1):
        dp1[i][b] = (pow(b - 1, i - a, MOD) + pow(b - 1, i - a - 1, MOD) * 1 * (i - a)) % MOD
        dp3[i][b] = (pow(b, i - a, MOD) - dp1[i][b]) % MOD
    for j in range(b + 1, d + 1):
        dp1[a][j] = (pow(a - 1, j - b, MOD) + pow(a - 1, j - b - 1, MOD) * 1 * (j - b)) % MOD
        dp2[a][j] = (pow(a, j - b, MOD) - dp1[a][j]) % MOD
    for i in range(a + 1, c + 1):
        for j in range(b + 1, d + 1):
            dp1[i][j] = ((dp1[i - 1][j] + dp2[i - 1][j]) * (j - 1)) % MOD
            dp2[i][j] = (dp2[i][j - 1] * i + dp1[i][j - 1] + dp3[i][j - 1]) % MOD
            dp3[i][j] = (dp3[i - 1][j] * j + dp1[i - 1][j] + dp2[i - 1][j]) % MOD

    # print(dp1, dp2, dp3)
    # print((dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD)
    return (dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD


def main():
    a, b, c, d = map(int, input().split())
    res = solve(a, b, c, d)
    print(res)


def test():
    assert solve(1, 1, 2, 2) == 3
    assert solve(1, 1, 3, 3) == 30
    assert solve(2, 1, 3, 4) == 65
    # assert solve(31, 41, 59, 265) == 387222020


if __name__ == "__main__":
    test()
    main()
### BUGGY CODE ###

n = int(input())
s = input()
sum = 0
for i in range(1, n-1):
  for j in range(i+1, n):
    if(s[i-1] == s[j-1]):
      continue
    k = {"R", "G", "B"} - {s[i-1], s[j-1]}
    k = k.pop()
    sum += s[j:].count(k)
    if(2*j-i-1 < n):
      if(s[2*j-i-1] == k):
        sum -= 1
print(sum)

### FIXED CODE ###

n = int(input())
s = input()
sum = s.count("R") * s.count("G") * s.count("B")
for i in range(1, n-1):
  for j in range(i+1, n):
    k = 2*j-i-1
    if(k >= n):
      break
    if(len({s[i-1], s[j-1], s[k]}) == 3):
        sum -= 1
print(sum)
### BUGGY CODE ###

from math import factorial as fact
import math
import fractions
import sys
import itertools
import numpy as np
from collections import Counter
import datetime
#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

def keta(N):
	return len(str(N))


def input_daytime(input_time):
	time,distance=input_time.split()
	t=time.split(":")
	se=str(t[-1]).split(".")
	dt1 = datetime.timedelta(hours=int(t[0]),minutes=int(t[1]),seconds=int(se[0]),milliseconds=int(se[1]))
	return dt1

def combinations(n,r):
	return list(itertools.combinations(n,r))

def all_sets(num_list):
	subsets=[]
	for i in range(2,len(num_list) + 1):
		for c in combinations(num_list, i):
			subsets.append(c) 
	return subsets

#公約数の列挙
def ch(x1,x2):
	cf=[]
	for i in range(2,min(x1,x2)+1):
		if x1 % i==0 and x2%i==0:
			cf.append(i)
	return cf

def CountOneRoots(x,y):
	#x:縦，y:横
	return fact(x+y)/fact(x)/fact(y)



A,B=input2()
ch=ch(A,B)
count=0
#素数を数える
for num in ch:
	flag=True
	for k in range(2, int(math.sqrt(num)) +1):
		if num%k==0:
			#素数ではない
			flag=False
	if flag==True:
		count+=1
print(count+1)




### FIXED CODE ###

from math import factorial as fact
import math
import fractions
import sys
import itertools
import numpy as np
from collections import Counter
import datetime
#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

def keta(N):
	return len(str(N))


def input_daytime(input_time):
	time,distance=input_time.split()
	t=time.split(":")
	se=str(t[-1]).split(".")
	dt1 = datetime.timedelta(hours=int(t[0]),minutes=int(t[1]),seconds=int(se[0]),milliseconds=int(se[1]))
	return dt1

def combinations(n,r):
	return list(itertools.combinations(n,r))

def all_sets(num_list):
	subsets=[]
	for i in range(2,len(num_list) + 1):
		for c in combinations(num_list, i):
			subsets.append(c) 
	return subsets

#公約数の列挙
def ch(x1):
	cf=[]
	for i in range(2,math.sqrt(x1)+1):
		if x1 % i==0:
			cf.append(i)
	return cf

def CountOneRoots(x,y):
	#x:縦，y:横
	return fact(x+y)/fact(x)/fact(y)

# 素因数分解
def factorization(n):
	tmp=n
	count=0
	for i in range(2,int(n**0.5)+2):
		if tmp%i==0:
			cnt=0
			while tmp%i==0:
				cnt+=1
				tmp//=i
			count+=1
	if tmp!=1:
		count+=1

	return count
			


A,B=input2()
gcd=fractions.gcd(A,B)
# ch=ch(gcd)
print(factorization(int(gcd))+1)
### BUGGY CODE ###

from bisect import bisect_left as bl
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    if K > max(A):
        print("IMPOSSIBLE")
        exit()
    if K in A:
        print("POSSIBLE")
        exit()
    key = bl(A,K)
    pre = A[key:]
    post = A[:key]
    for a in pre:
        if a-K in A:
            print("POSSIBLE")
            exit()
    B = map(lambda x:x%2,A)
    B = set(B)
    flag = 0
    for i in range(N-1):
        if A[i+1] - A[i] not in A:
            flag = 1
    if len(B) == 2 and flag:
        print("POSSIBLE")
        exit()
    print("IMPOSSIBLE")
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    if K > max(A):
        print("IMPOSSIBLE")
        exit()
    if K in A:
        print("POSSIBLE")
        exit()

    E = list(map(lambda x:abs(x-K),A))
    E = set(E)
    C = [A[i+1]-A[i] for i in range(N-1)]
    C = set(C)
    D = set(A)
    if E&D:
        print("POSSIBLE")
        exit()

    print("IMPOSSIBLE")
    

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

# 未完成
import numpy as np
import sys
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = []
if N == 1:
    print(1)
    sys.exit()

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        if (diff_x, diff_y) not in kouholist:
            kouholist.append((diff_x, diff_y))

for list_i in kouholist:
    ans_kari = 0
    for r in range(N):
        for q in range(N):
            if x[q] - x[r] == list_i[0] and y[q] - y[r] == list_i[1]:
                ans_kari += 1
    ans.append(ans_kari)

print("{}".format(N-max(ans)))


### FIXED CODE ###

# 未完成

import sys
N = int(input())
x = [0]*N
y = [0]*N
kouholist = []
ans = N
if N == 1:
    print(1)
    sys.exit()

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = N
        for r in range(N):
            for q in range(N):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans_kari -= 1
        if ans_kari < ans:
            ans = ans_kari

print("{}".format(ans))
### BUGGY CODE ###


def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] > par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1]
    
    while par[frm][0] != par[par[frm][0]][0]:
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def is_match(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(input())

points = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([i,i,[x,y]])
edges = []
for i in range(N-1):
    for j in range(i+1,N):
        edges.append((manhattan(points[i][2], points[j][2]), i, j))
edges.sort(key=lambda x:x[0])
cost = 0
for i in range(len(edges)):
    # print(edges[i], is_match(points, edges[i][1]), is_match(points, edges[i][2]),points)
    if is_match(points, edges[i][1]) == is_match(points, edges[i][2]):
        # print()
        continue
    cost += edges[i][0]
    update_tree(points, edges[i][1], edges[i][2])
print(cost)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def unite(i, j):
    j = get_par(j)
    par[j] = get_par(i)
    return

def get_par(p):
    if par[p] is None:
        return p
    par[p] = get_par(par[p])
    return par[p]

N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([x,y,i])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][0] - points[i+1][0]), points[i][2], points[i+1][2]))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][1] - points[i+1][1]), points[i][2], points[i+1][2]))
edges.sort(key=lambda x:x[0], reverse=True)

par = [None] * N
cost = 0
count = 0
points.sort()
while count < N - 1:
    c, i, j = edges.pop()
    if get_par(i) == get_par(j):
        continue
    unite(i, j)
    cost += c
    count += 1
print(cost)
### BUGGY CODE ###

n,q = map(int, input().split())
ABPX = [tuple(map(int,input().split())) for i in range(q+n-1)]
AB = iter(ABPX[:n-1])
PX = iter(ABPX[n-1:])

tree = dict()
for a,b in AB:
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

opr = {i+1:0 for i in range(n)}
for p,x in PX:
  opr[p] += x

stack = [1]
parent = [0] * (n+1)
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x]: continue
    parent[y] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

print(*ans)

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,q = map(int, input().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:n+n-2])
PX = iter(ABPX[n+n-2:])

tree = dict()
for a,b in zip(AB,AB):
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

opr = {i+1:0 for i in range(n)}
for p,x in zip(PX,PX):
  opr[p] += x

stack = [1]
parent = [0] * (n+1)
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x]: continue
    parent[y] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

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

S = input()
T = input()
lenS = len(S)
lenT = len(T)
"""
dp[i][j] -> Sのi文字目までみる、Tのj文字目まで見るときの最長共通部分列の長さ
if S[i] == T[i]:
    dp[i][j] = dp[i-1][j-1]+1
else:
    dp[i][j] = max(dp[i-1][j],dp[i][j-1])

で最長もとめて、最後に復元していく。
"""
dp = [[0]*(lenT) for _ in range(lenS)]
for i in range(lenS):
    for j in range(lenT):
        if S[i]==T[j]:
            if i==0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

m = lenS-1
n = lenT-1
ans = []
while n!=-1 and m!=-1:
    if m == 0 and dp[m][n] == 1:
        ans.append(S[m])
        m -= 1
        continue
    if n == 0 and dp[m][n] == 1:
        ans.append(T[n])
        n -= 1
        continue
    if dp[m][n] == dp[m-1][n]:
        m -= 1
        continue
    if dp[m][n] == dp[m][n-1]:
        n -= 1
        continue
    ans.append(S[m])
    m-=1
    n-=1

ans = ans[::-1]
print("".join(ans))

### FIXED CODE ###

# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(int(input()) for i in range(M))
MOD = 10 ** 9 + 7
DP = [0] * (N + 10)
if 1 not in A:
    DP[1] = 1
if 2 not in A and 1 in A:
    DP[2] = 1
if 2 not in A and 1 not in A:
    DP[2] = 2
for i in range(3, N + 1):
    if i not in A:
        DP[i] = (DP[i - 1] + DP[i - 2]) % MOD
print(DP[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = set(int(input()) for i in range(M))
MOD = 10 ** 9 + 7
DP = [0] * (N + 10)
if 1 not in A:
    DP[1] = 1
if 2 not in A and 1 in A:
    DP[2] = 1
if 2 not in A and 1 not in A:
    DP[2] = 2
for i in range(3, N + 1):
    if i not in A:
        DP[i] = (DP[i - 1] + DP[i - 2]) % MOD
print(DP[N])
### BUGGY CODE ###

n = int(input())
a=list(map(int,input().split()))

for i in range(1,n+1):
    print(a.index(i)+1)

### FIXED CODE ###

n = int(input())
a=list(map(int,input().split()))

s=sorted(range(len(a)), key=lambda k: a[k])

for i in range(n):
    print(s[i]+1)
### BUGGY CODE ###

import math

a=input()
a=int(a)
sum=0

def gcda(x,y,z):
    temp=math.gcd(x,y)
    return math.gcd(temp,z)

for i in range(1,a+1):
    for j in range(1,a+1):
        for k in range(1,a+1):
            sum+=gcda(i,j,k)

print(sum)


### FIXED CODE ###

import math

a=input()
a=int(a)
sum=0

def gcda(x,y,z):
    temp=math.gcd(x,y)
    return math.gcd(temp,z)

for i in range(1,a+1):
    for j in range(1,a+1):
        for k in range(1,a+1):
            sum+=gcda(i,j,k)

print(sum)