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

N = int(input())
lst = []
for i in range(N):
    x, y = map(int, input().split())
    lst.append([x, y, i])

def prim():
    import heapq
    used = [False] * N
    edgelist = []
    for i in lst:
        heapq.heappush(edgelist, [min(abs(lst[0][0]-i[0]), abs(lst[0][1]-i[1])), i[2]])
    used[0] = True
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        v = minedge[1] #今回追加される頂点
        if used[v]: #使われているとき
            continue
        used[v] = True #使われたことにする
        # print (minedge[0])
        res += minedge[0]
        for i in lst:
            if not used[i[2]]:
                heapq.heappush(edgelist, [min(abs(lst[v][0]-i[0]), abs(lst[v][1]-i[1])), i[2]])
    return res

print (prim())





### FIXED CODE ###

class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

N = int(input())

lst = []
for i in range(N):
    x, y = map(int, input().split())
    lst.append([x, y, i])
# print (lst)
edge = []
lst.sort(key = lambda x: x[0])
for i in range(1, N):
    edge.append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])
# print (edge)
lst.sort(key = lambda x: x[1])
for i in range(1, N):
    edge.append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])
# print (edge)
edge.sort(key = lambda x: x[2])

uni = UnionFind(N)
ans = 0
for i in edge:
    if not uni.same(i[0], i[1]): #違うグループのとき
        uni.connect(i[0], i[1])
        ans += i[2]
print (ans)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append([int(x) for x in input().split()])
B = [[True for i in range(N)] for j in range(N)]
A_sum = 0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if i != k and j != k:
        if A[i][j] > (A[i][k] + A[k][j]):
          A_sum = -2
        if A[i][j] == (A[i][k] + A[k][j]):
          B[i][j] = False
          B[j][i] = False
if A_sum >= 0:
  for i in range(N):
    for j in range(N):
      if B[i][j]:
        A_sum += A[i][j]
print(A_sum // 2)

### FIXED CODE ###

import heapq
N = int(input())
A = [[] for i in range(N)]
Q = []
for i in range(N):
  A[i] = [int(x) for x in input().split()]
  for j in range(i + 1, N):
    heapq.heappush(Q, [A[i][j], i, j])
G = [[10 ** 9 + 1 for j in range(N)] for i in range(N)]
for i in range(N):
  G[i][i] = 0
cnt = 0
while Q:
  [d, s, t] = heapq.heappop(Q)
  add = True
  for k in range(N):
    if d > G[s][k] + G[k][t]:
      break
    if d == G[s][k] + G[k][t]:
      add = False
  else:
    G[s][t] = d
    G[t][s] = d
    cnt += d if add else 0
    continue
  print(-1)
  break
else:
  print(cnt)
### BUGGY CODE ###

x = int(input())

ans = x

while True:
  for i in range(2, ans):
    if ans % i == 0:
      continue
  else:
    print(ans)
  ans += 1

### FIXED CODE ###

import math

x = int(input())
 
ans = x
 
while True:
  for i in range(2, int(math.sqrt(ans))):
    if ans % i == 0:
      break
  else:
    print(ans)
    exit()
  ans += 1
### BUGGY CODE ###

[n,k]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))


for i in range(k):
    imos=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        imos[kagen]+=1
        if jogen+1<n:
            imos[jogen+1]-=1
    akarusanext=imos
    for j in range(1,n):
        akarusanext[j]+=akarusanext[j-1]
    
    if akarusa==akarusanext:
        break
    else:
        akarusa=akarusanext

for i in range(n):
    print(akarusa[i], end=" ")


### FIXED CODE ###

[n,k]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))


for i in range(k):
    imos=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        imos[kagen]+=1
        if jogen+1<n:
            imos[jogen+1]-=1
    akarusanext=imos
    for j in range(1,n):
        akarusanext[j]+=akarusanext[j-1]
    
    if akarusa==akarusanext:
        break
    else:
        akarusa=akarusanext

for i in range(n):
    print(akarusa[i], end=" ")
### BUGGY CODE ###

S = input()
listS = list(S)

for i in range(len(listS)):
	if listS[i] == "B":
		listS[i] = 0
	if listS[i] == "W":
		listS[i] = 1
		
done = False

listX = []
listN = []

while not done:
	for i in range(len(listS)-1):
		if listS[i] < listS[i+1]:
			listS[i] = 1
			listS[i+1] = 0
			listN.append(0)
			listX.append(0)

	if len(listX) == 0:
		print(len(listN))
		done = True
	listX.clear()




### FIXED CODE ###

s = input()
s = list(s)


w_sum = 0
w_n = 0
for i, c in enumerate(s):
    if c == "W":
        w_sum += i
        w_n += 1
    
print(w_sum - w_n*(w_n-1)//2)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x,d):
        d[x] = 0
        for y in v[x]:
            if d[y]:
                size[x] += dfs(y,d)
        return size[x]

    n = I()
    v = [[] for i in range(n)]
    size = [1]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    dfs(0,d)
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[0]-size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque([0])
    d = [0]*n
    d[0] = 1
    pre = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                pre[y] = x
                q.append(y)
    V = list(range(1,n))
    V.sort(key = lambda x:-d[x])
    size = [1]*n
    for i in V:
        size[pre[i]] += size[i]
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

i = 1

while True:
    x = 'i+1(raw_input())'
    if x == 0:
        break
    print ("case {0}: {1}").format(i,x)
    i = i+1

### FIXED CODE ###

def main():
    loop_count = 0
    while 1:
        loop_count +=1
        param = raw_input()
        if param == "0":
            break
        else:
            print "Case %s: %s" % (loop_count,param)

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

N = int(input())
S = input()
ans = S.count("R")*S.count("G")*S.count("B")

for i in range(N-2):
  for j in range(i+1,N-1):
      k = 2*j-i
      if k<=j:
        continue
      else:
        if N>k and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
          ans-=1
          
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R")*S.count("G")*S.count("B")

for i in range(N-2):
  for j in range(i+1,N-1):
      k = 2*j-i
      if k>=N:
        break
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans-=1
          
print(ans)
### BUGGY CODE ###

import numpy as np

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

a = []
for i in range(N):
    ai = []
    for j in range(N):
        k = i+1 if i+1 < N else 0
        if(j == i or j == k):
            ai.append(1)
        else:
            ai.append(0)
    a.append(ai)

a_matrix = np.array(a)
b_matrix = np.array(A)

x = np.linalg.solve(a_matrix,b_matrix)

x = x * 2

for i in range(N):
    print(int(x[i]),end="")
    if(i != N-1):
        print(" ",end="")
print()


### FIXED CODE ###

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

x=[]
s=sum(a)
x.append(s-2*sum(a[1::2]))
for i in range(1,n-1):
    x.append(2*a[i-1]-x[i-1])
x.append(2*a[n-1]-x[0])
print(*x)
### BUGGY CODE ###

N = int(input())
s = []
ans = 0
for i in range(N):
    s.append(''.join(sorted(input())))
    if i != 0:
        for j in range(i):
            if s[i] == s[j]:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]

ans = 0
d = {}
for i in s:
    if i in d:
        ans += d[i]
        d[i] += 1
    else:
        d[i] = 1
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
a=M//N
x=1
if a>0:
    for i in reversed(range(1,a+1)):
        if M%i==0:
            x=i
            break
print(x)


### FIXED CODE ###

N,M=map(int,input().split())
a=M//N
x=1
for i in range(1,a+1):
    if M%i==0:
        x=i
        if (M//i)>i and (M//i)<=a:
            x=M//i
            break
print(x)
### BUGGY CODE ###

T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))
    
for N, A, B, C, D in caseList:
    dic = {N: 0}
    
    minAns = 999999999999
    searchSet = set([N])

    count = 0
    k=N
    while True:
        tmpSet = set()

        v = dic[k]

        if k == 1:
            continue

        # A
        if k % 2 == 0:
            dic[k // 2] = dic.get(k // 2, minAns)
            if dic[k // 2] > v + A:
                dic[k // 2] = v + A
                tmpSet.add(k // 2)

        # B
        if k % 3 == 0:
            dic[k // 3] = dic.get(k // 3, minAns)
            if dic[k // 3] > v + B:
                dic[k // 3] = v + B
                tmpSet.add(k // 3)

        # C
        if k % 5 == 0:
            dic[k // 5] = dic.get(k // 5, minAns)
            if dic[k // 5] > v + C:
                dic[k // 5] = v + C
                tmpSet.add(k // 5)

        # D
        dic[k + 1] = dic.get(k + 1, minAns)
        if dic[k + 1] > v + D:
            dic[k + 1] = v + D
            tmpSet.add(k + 1)

        dic[k - 1] = dic.get(k - 1, minAns)
        if dic[k - 1] > v + D:
            dic[k - 1] = v + D
            tmpSet.add(k - 1)

        del dic[k]
        k=min(dic, key=dic.get)


        count += 1
        if 1 in dic.keys():
            if minAns > dic[1] + D:
                minAns = dic[1] + D
            #             print(minAns)
            else:
                break
    print(minAns)

### FIXED CODE ###

from functools import lru_cache

T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))


@lru_cache(maxsize=None)
def solve(n, A, B, C, D):
    if n == 0:
        return 0
    if n == 1:
        return D
    if n == 2:
        return min(D + D, A + D)

    ans = n * D

    for num, cost in zip([2, 3, 5], [A, B, C]):
        ans = min(
            solve((n + (num - n % num)) // num, A, B, C, D) + cost + D * (num - n % num),
            solve((n - n % num) // num, A, B, C, D) + cost + D * (n % num),
            ans,
        )

    return ans


for N, A, B, C, D in caseList:
    print(solve(N, A, B, C, D))
### BUGGY CODE ###


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


N=int(input())

S=[]
S_count=dict()
fixed_count=dict()
for n in range(N):
    s=input()
    s=''.join(sorted(s))
    if s in S:
        S_count[s]+=1
    else:
        S_count[s]=1
    S.append(s)

for k in S_count.keys():
    if S_count[k]>1:
        fixed_count[k]=S_count[k]

key=fixed_count.keys()

total=0

for k in key:
    t=fixed_count[k]
    total+=cmb(t,2)

print(total)

### FIXED CODE ###


N=int(input())
S=[]
total=0

for s in range(N):
    tmp=input()
    S.append("".join(sorted(tmp)))

S=sorted(S)
S_key=list(set(S))
count=[0]*len(S_key)
S_dict=dict(zip(S_key,count))


for s in S:
    total+=S_dict[s]
    S_dict[s]+=1

print(total)
### BUGGY CODE ###

n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
W_MAX = s
dp = [0]*(W_MAX+1)
dp[0] = 1
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(W_MAX+1)):
        if W_MAX < j+a:
            continue
        dp[j+a] += dp[j]*inv_2

print(dp[-1]*pow(2, n, MOD) % MOD)

### FIXED CODE ###

n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
W_MAX = s
dp = [0]*(W_MAX+1)
dp[0] = 1
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(W_MAX+1)):
        if W_MAX < j+a:
            continue
        dp[j+a] += dp[j]*inv_2
        dp[j+a] %= MOD

print(dp[-1]*pow(2, n, MOD) % MOD)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
P = list(map(int, input().split()))
ans=1
while len(P)!=1 :
    k=P.index(min(P))
    if k ==0:
        break
    P=P[0:k:1]
    ans+=1
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
P = list(map(int, input().split()))
ans=1
if N!=1:
    M=P[0]
    for i in range(1,N,1):
        M=min(P[i],M)
        if P[i] ==M:
            ans+=1
print(ans)
### BUGGY CODE ###

A, B, N = [int(x) for x in input().split()]

val = (int(A * i / B) - A * int(i / B) for i in range(1, N+1))
print(max(val))


### FIXED CODE ###

A, B, N = [int(x) for x in input().split()]

# val = (int(A * i / B) - A * int(i / B) for i in range(1, N+1))
# print(max(val))

x = B - 1
if x > N:
    x = N
print(int(A * x / B) - A * int(x / B))
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

n = int(input())
A = [int(a) for a in input().split()]

ans = []
for i in range(len(A)):
    tmp = A[i]
    L = reduce(gcd, [0] + A[:i])
    R = reduce(gcd, A[i+1:] + [0])
    ans.append(gcd(L,R))
        
print(max(ans))

### FIXED CODE ###

from functools import reduce
from fractions import gcd

n = int(input())
A = [int(a) for a in input().split()]

l = [0 for _ in range(n+1)]
r = [0 for _ in range(n+1)]
ans = []

for i in range(n):
    l[i+1] = gcd(l[i],A[i])

for i in range(n-1,-1,-1):
    r[i-1] = gcd(r[i],A[i])
    
for i in range(n):
    ans.append(gcd(l[i],r[i]))
    
print(max(ans))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = 1
    for x in A:
        S *= x

    def factorization(n):
        ret = set()
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                ret.add(i)

        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            flag = False
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()
### BUGGY CODE ###

#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict

def main():
    N = int(input())
    As = [int(x) for x in input().split()]

    d = defaultdict(int)

    for i in range(N):
        d[As[i]] += 1
    
    for i in range(N):
        ans = 0
        for k in d.keys():
            j = d[k]
            if (k == As[i]):
                j -= 1
            if j > 1:
                ans += j*(j-1)//2
        print(ans)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc159","d",main)

### FIXED CODE ###

#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict

def main():
    N = int(input())
    d = defaultdict(int)
    As = list(map(int, input().split()))
    for i in range(N):
        d[As[i]] += 1
    
    ans = 0
    for k in d.keys():
        j = d[k]
        if j > 1:
            ans += j*(j-1)//2

    for i in range(N):
        j = d[As[i]]
        print(ans+1-j)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc159","d",main)
### BUGGY CODE ###

from bisect import bisect_left
p = 10**9+7
N = int(input())
A = []
for i in range(N):
    a = int(input())
    if len(A)==0:
        A.append(a)
    else:
        if a==A[-1]:continue
        else:
            A.append(a)
N = len(A)
C = {}
for i in range(N):
    c = A[i]
    if c not in C:
        C[c] = []
    C[c].append(i)
dp = [1 for _ in range(N)]
for i in range(1,N):
    dp[i] = dp[i-1]
    a = A[i]
    ind = bisect_left(C[a],i)
    if ind>0:
        for j in range(ind-1,-1,-1):
            if C[a][j]>=1:
                dp[i] = (dp[i]+dp[C[a][j]-1])%p
            else:
                dp[i] = dp[i]+1
print(dp[N-1])

### FIXED CODE ###

from bisect import bisect_left
p = 10**9+7
N = int(input())
C = [int(input()) for _ in range(N)]
A = [0 for _ in range(N)]
B = {i:[0,-1] for i in range(1,2*10**5+1)}
for i in range(N):
    c = C[i]
    if B[c][-1]==i-1:
        A[i] = 0
    else:
        A[i] = 1
    B[c].append(i)
dp = [0 for _ in range(N+1)]
dp[1] = 1
for i in range(1,N):
    if A[i]==1:
        ind = bisect_left(B[C[i]],i)
        j = B[C[i]][ind-1]
        dp[i+1] = (dp[i]+dp[j+1])%p
    else:
        dp[i+1] = dp[i]
print(dp[N])
### BUGGY CODE ###

import sys, copy

def wf(d):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j] = min(d[i][j],d[i][k]+d[k][j])
  return d

N,M,R = map(int,input().split())
Rs = list(map(int,input().split()))

d = [[float('inf') for i in range(N)] for i in range(N)]
for _ in range(M):
  a,b,c = map(int,sys.stdin.readline().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c

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

wf(d)

from collections import deque

ans = float('inf')
for start_i in Rs:
  q = deque()
  q.append([start_i-1,0,set([start_i-1])])
  while len(q) > 0:
    prv_node, prv_cost, done = q.pop()

    min_cost = float('inf')
    min_nodes = []
    for r in Rs:
      r -= 1
      if r in done: continue
      if min_cost > d[prv_node][r]:
        min_cost = d[prv_node][r]
        min_nodes = [r]
      elif min_cost == d[prv_node][r]:
        min_cost = d[prv_node][r]
        min_nodes.append(r)
    
    for node in min_nodes:   
      tmp_done = copy.deepcopy(done)
      tmp_done.add(node)
      if len(tmp_done) == R:
        if ans > prv_cost+min_cost: ans = prv_cost+min_cost
      else: q.append([node, prv_cost+min_cost, tmp_done])

print(ans)

### FIXED CODE ###

import sys, copy
from itertools import permutations

def wf(d):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j] = min(d[i][j],d[i][k]+d[k][j])
  return d

N,M,R = map(int,input().split())
Rs = list(map(int,input().split()))

d = [[float('inf') for i in range(N)] for i in range(N)]
for _ in range(M):
  a,b,c = map(int,sys.stdin.readline().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c

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

wf(d)

ans = float('inf')
for prm in permutations(Rs, R):
  ans = min(ans, sum([d[prm[i-1]-1][prm[i]-1] for i in range(1,R)]))
print(ans)
### BUGGY CODE ###

import math

K = int(input())
ans = 0

for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      temp = math.gcd(i, j)
      temp2 = math.gcd(temp, k)
      ans = temp2 + ans

print(ans)


### FIXED CODE ###

import math
from functools import reduce

K = int(input())
ans = 0

def main(K):
    g=0
    for i in range(1,K+1):
        for j in range(1,K+1):
            for k in range(1,K+1):
                g += math.gcd(math.gcd(i, j), k)
    return (g)
 
print(main(K))