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

n = int(input())
s = 0
for i in range(len(str(n))):
    r = n % 10
    s += r
    s %= 9
    n //= 10
if s % 9 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
ln = list(str(n))
from collections import Counter
nc = dict(Counter(ln))
s = 0
if n != 0:
    for i in range(1, 10):
        if str(i) in nc:
            s += i * nc[str(i)]
if s % 9 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from itertools import combinations

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

for c in list(combinations(A, 2)):
    tmp = 1
    for e in c:
        tmp *= e
    ans += tmp % (10**9 + 7)

print(ans % (10**9 + 7))

### FIXED CODE ###

import sys

input = sys.stdin.readline

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

A_sum_s = sum(A) ** 2

for e in A:
    A_sum_s -= e ** 2
print(A_sum_s // 2 % (10**9 + 7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
import numpy as np

n, m = map(int, input().split())
*a, = map(int, input().split()) 

a = np.array(a)
tmp = (a/2).astype(np.int)

import fractions

def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt

cnt = f(a[0])
for i in range(1, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    lcm = tmp[0]
    for i in range(1, n):
        lcm = lcm * tmp[i] // fractions.gcd(lcm, tmp[i])
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
*a, = map(int, input().split()) 

a = [ai >> 1 for ai in a]

import fractions
from functools import reduce

def getLCM(a, b):
    return a * b // fractions.gcd(a, b)

def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt

cnt = f(a[0])
for i in range(1, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    lcm = reduce(lambda x, y: getLCM(x, y), a)
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)
### BUGGY CODE ###

x=int(input())
a=int(input())
b=int(input())

af=x-a

while af>0:
    af-b

print(af)

### FIXED CODE ###

x=int(input())
a=int(input())
b=int(input())

ans=x-a

while ans>=b:
    ans=ans-b

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

n = int(input())
p = list(map(int,input().split()))
c = 0

for i in range(n):
    s = p[:i+1]
#sの最小値とsの末尾が一致するかどうか
    if s[-1] == min(s):
        c += 1
        
print(c)


### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
c = 0
m = 10**9
for i in range(n):
    if p[i] < m:
        m = p[i]
        c += 1
        
print(c)
### BUGGY CODE ###

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

ans = 1
for i in range(N):
    ans *= A[i]
    if 0 == A[i]:
        break
if 10 ** 18 < ans:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
else:
    for i in range(N):
        ans *= A[i]
        if 10 ** 18 < ans:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

N = int(input()) # 各リストの数
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A = sorted(A, reverse=False)
A.insert(0, 0)
A.append(float('inf'))
B = sorted(B, reverse=False)
# A > B > Cである組み合わせの数を求める

count = 0
for ic in range(N):
    bottom_a = 0
    for ib in range(N):
        if B[ib] >= C[ic]:
            break
        
        top_a = N
        count_a = 0
        while top_a >= bottom_a:
            middle_a = (top_a + bottom_a) // 2

            if A[middle_a] == B[ib]:
                count_a = middle_a - 1
                break
            if A[middle_a] < B[ib] and B[ib] < A[middle_a + 1]:
                count_a = middle_a
                break
            if A[middle_a] > B[ib]:
                top_a = middle_a
            if A[middle_a] < B[ib]:
                bottom_a = middle_a + 1

        count += count_a
        bottom_a = count_a

print(count)


### FIXED CODE ###

import bisect
import itertools

N = int(input()) # それぞれのパーツの数
A = list(map(int, input().split())) # 小さい
B = list(map(int, input().split())) # 中くらい
C = list(map(int, input().split())) # 大きい

# Cは並び替え不要
A.sort()
B.sort()

# Bの各要素でAを二分探索して返ってきたindexを先に保有しておく
b_counts = [0] * N
for i in range(N):
    b_count = bisect.bisect_left(A, B[i])
    b_counts[i] = b_count

cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts

# Cの各要素でBを二分探索。上記で保有しておいたb_countsを活用する
total = 0
for c in C:
    count = bisect.bisect_left(B, c)
    total += cumsum_b_counts[count]

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

n, t = map(int, input().split())
a = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
  x, y = map(int, input().split())
  a[i][0], a[i][1] = x, y
a = sorted(a, key=lambda x: x[0], reverse=True)
dp = [[0 for i in range(t+1)] for j in range(n+1)]

for i in range(1, n+1):
  for j in range(1, t+1):
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    if j == 1:
      dp[i][j] = max(dp[i][j], a[i-1][1])
    if j >= a[i-1][0]:
      dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1][0]] + a[i-1][1])
print(dp[n][t])  

### FIXED CODE ###

n, t = map(int, input().split())
a = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
  x, y = map(int, input().split())
  a[i][0], a[i][1] = x, y
a = sorted(a, key=lambda x: x[0], reverse=True)
dp = [[0 for i in range(t+1)] for j in range(n+1)]

for i in range(1, n+1):
  for j in range(1, t+1):
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    if j == 1:
      dp[i][j] = max(dp[i][j], a[i-1][1])
    if j >= a[i-1][0]:
      dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1][0]] + a[i-1][1])
print(dp[n][t])
### BUGGY CODE ###

import itertools
def w_f(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())
LR = map(int,input().split())
d = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 

D = w_f(d)
lr = list(itertools.permutations(LR))
ans = float("inf")
for li in lr:
    jd = 0
    for i in range(r-1):
        jd += D[li[i]-1][li[i+1]-1]
    
    if jd < ans:
        ans = jd
print(ans)
           

### FIXED CODE ###

import itertools
def w_f(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())
LR = map(int,input().split())
d = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 

D = w_f(d)
lr = list(itertools.permutations(LR))
ans = float("inf")
for li in lr:
    jd = 0
    for i in range(r-1):
        jd += D[li[i]-1][li[i+1]-1]
    
    if jd < ans:
        ans = jd
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())
S = []
for i in range(1,len(s)+1):
    for j in range(len(s)):
        if j+1 > len(s):
            break
        if s[j:j+i] not in  S:
            S.append(s[j:j+i])
S.sort()
print(S[K-1])


### FIXED CODE ###

s = input()
K = int(input())
t = set()

for k in range(1, K+1):
    for j in range(len(s)):
        if j+k == len(s)+1:
            break
        t.add(s[j:j+k])
t = sorted(t)
print(t[K-1])
### BUGGY CODE ###

k = int(input())
if k % 2 == 0:
    print("-1")
else:
    seven = "7"
    point = False
    for i in range(1000000):
        if int(seven) % k == 0:
            point = True
            break
        else:
            seven += "7"
    if point:
        print(len(seven))
    else:
        print("-1")

### FIXED CODE ###

k = int(input())
ans = -1
x = 7 % k
if not k%2 == 0:
    for i in range(1, k+1):
        if x == 0:
            ans = i
            break
        x = (x * 10 + 7) % k


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

import fractions

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

def gcd(l):
    ans = l[0]
    for i in range(1, N-1):
        ans = fractions.gcd(ans, l[i])
    return ans

max_res = -1
for i in range(N):
    A_removed = A[0:i] + A[i+1:N]
    res = gcd(A_removed)
    if (res>max_res):
        max_res = res

print(max_res)


### FIXED CODE ###

import fractions
import numpy as np

N = int(input())
A = np.array(sorted([int(i) for i in input().split()]))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

divisors=make_divisors(A[0])
divisors_1=make_divisors(A[1]) 
divisors.extend(divisors_1)

def gcd(l):
    ans = l[0]
    for j in range(1, N-1):
        ans = fractions.gcd(ans, l[j])
    return ans

#res = 1
for i in sorted(list(set(divisors))):
#    print("{} / {}".format(i, A%i))
#    print(np.where(A%i != 0))
#    print((A%i != 0))
    if(np.sum(A%i != 0)<=1):
        #print(i)
        res = i


print(res)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))

for i in range(m):
    a = A.pop(-1)
    a /= 2
    bisect.insort_left(A, a)

A = map(int, A)

print(sum(A))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
A = sorted(list(map(lambda x: int(x)*(-1), input().split())))

heapq.heapify(A)

for i in range(m):
    a = heapq.heappop(A)
    a = a * (-1) // 2
    heapq.heappush(A, -a)

print(-sum(A))
### BUGGY CODE ###

n, k = map(int, input().split())
alst = list(map(int, input().split()))

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if min(alst) == n:
        break
print(*alst)

### FIXED CODE ###

n, k = map(int, input().split())
alst = list(map(int, input().split()))

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if tmp[0] == n and tmp[-1] == -n:
        break
print(*alst)
### BUGGY CODE ###

n=int(input())
l=[0]*(n+1)
ans=0
for i in range(1,n+1):
  j=i
  while(j<=n):
    l[j]+=1
    j+=i
  
  ans+=i*l[i]
print(ans)



### FIXED CODE ###

n=int(input())
ans = 0
for i in range(1, n+1):
    a = n//i
    ans += a*(a+1)//2*i
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int,input().split())
grid = [list(input()) for _ in range(H)]
w_cnt = 0
for i in range(H):
    w_cnt += grid[i].count('.')


d = [[-1]*W for _ in range(H)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]


que = deque()
for x in range(W):
    for y in range(H):
        if grid[y][x] == '#':
            d[y][x] = 0
            que.append([x,y])

while len(que) != 0:
    p = que.popleft()
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        #print(nx,ny)
        if 0 <= nx <= W-1 and 0 <= ny <= H-1 and grid[ny][nx] == '.' and d[ny][nx] == -1:
            que.append([nx,ny])
            d[ny][nx] = d[p[1]][p[0]] + 1

# print(d)
# print(d[H-1][W-1])
res = 0
for x in range(W):
    for y in range(H):
        res = max(res,d[y][x])
print(res)


### FIXED CODE ###

from collections import deque
H, W = map(int,input().split())
grid = [list(input()) for _ in range(H)]


d = [[-1]*W for _ in range(H)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]


que = deque()
for x in range(W):
    for y in range(H):
        if grid[y][x] == '#':
            d[y][x] = 0
            que.append([x,y])

while len(que) != 0:
    p = que.popleft()
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        #print(nx,ny)
        if 0 <= nx <= W-1 and 0 <= ny <= H-1 and grid[ny][nx] == '.' and d[ny][nx] == -1:
            que.append([nx,ny])
            d[ny][nx] = d[p[1]][p[0]] + 1

# print(d)
# print(d[H-1][W-1])
res = 0
for x in range(W):
    for y in range(H):
        res = max(res,d[y][x])
print(res)
### BUGGY CODE ###

from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<=x<j
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        que.append((state[c-1],i+1))
        state[c-1]=i+1

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

seg=BIT(N+1)
ans=[0]*Q



for i in range(len(que)):
    while query and query[-1][1]<que[i][1]:
        q=query.pop()
        l,r,j=q
        ans[j]=r-l+1-(seg.get(l-1,r))

    now=que[i]
    l, r=now  # index
    #A[l]+=1
    seg.add(l, 1)

    while query and query[-1][1]==r:
        q=query.pop()
        lq,rq,j=q
        
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.query(lq,rq+1))
        #print(seg.get(lq,rq+1))

while query:
    q=query.pop()
    lq,rq,j=q     
    ans[j]=rq-lq+1-(seg.get(lq-1,rq))
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


### FIXED CODE ###

from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)
### BUGGY CODE ###

from collections import Counter
from scipy.misc import comb
N = int(input())
A = input().split()
C = Counter(A)
def banned_count(seq):
    for i in range(N):
        C[A[i]] -= 1
        print(sum([comb(j, 2, exact=True) for j in C.values()]))
        C[A[i]] += 1
banned_count(A)

### FIXED CODE ###

from collections import Counter
from scipy.misc import comb
N = int(input())
A = input().split()
C = Counter(A)
s = sum([comb(j, 2, exact=True) for j in C.values()])
for i in range(N):
    print(s-C[A[i]]+1)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
count = 0
for a in range(N+1):
    for b in range(N-a+1):
        c = N-a-b
        if a%R == 0 and b%G == 0 and c%B == 0:
            count +=1
print(count)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
count = 0
for a in range(0,N+1,R):
    if a%R == 0:
        for b in range(0,N-a+1,G):
            if b%G == 0:
                c = N-a-b
                if c%B == 0:
                    count +=1
print(count)
### BUGGY CODE ###

import sys
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
xlist = []
ylist = []
for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])

xroot = [[] for _ in range(N+1)]
yroot = [[] for _ in range(N+1)]

xlist.sort() # [x, ID]
ylist.sort() # [y, ID]

for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  costx = nextx - x
  xroot[xID].append([costx, nextxID])
  xroot[nextxID].append([costx, xID])

  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  costy = nexty - y
  yroot[yID].append([costy, nextyID])
  yroot[nextyID].append([costy, yID])
#print(xroot) # [cost, rootID]
#print(yroot)

hpop = heapq.heappop
hpush = heapq.heappush
data = [] # [val, ID]

visited = [False]*(N+1)
hpush(data, [0, 1])
ans = 0
while data:
  val, num = hpop(data)
  if visited[num] == False:
    visited[num] = True
    #print(val, num)
    ans += val
    for i in xroot[num]:
      if visited[i[1]] == False:
        hpush(data, i)
    for j in yroot[num]:
      if visited[j[1]] == False:
        hpush(data, j)
print(ans)

### FIXED CODE ###

import sys
from operator import itemgetter
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort(key=itemgetter(0))
ylist.sort(key=itemgetter(0))

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  node.append([nextx - x, xID, nextxID])
  node.append([nexty - y, yID, nextyID])
node.sort(key=itemgetter(0), reverse=True)

ans = 0
while node:
  val, i, j = node.pop()
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
P = [int(x) for x in input().split()]
ans = 0
for i in range(N-K+1):
    l = sum(P[i:i+K])
    if l > ans:
        ans = l
ans = ans + K
print(ans/2)

### FIXED CODE ###

N,K = map(int,input().split())
P = [int(x) for x in input().split()]
L = []
l = 0
for i in range(N):
    l += P[i]
    L.append(l)
ANS = []
ANS.append(L[K-1])
for i in range(N-K):
    ANS.append(L[i+K] - L[i])
ans = max(ANS) + K
print(ans/2)
### BUGGY CODE ###

s = input()
k = int(input())
l = len(s)
substr = set()

for i in range(0,l):
    for j in range(i+1,l+1):
        substr.add(s[i:j])

substr = sorted(list(substr))
print(substr[k-1])

### FIXED CODE ###

s = input()
K = int(input())
idx = [[] for _ in range(26)]

for i in range(len(s)):
    idx[ord(s[i])-ord("a")].append(i)

substr = set()
for i in range(26):
    for j in idx[i]:
        for k in range(j+1,j+6):
            substr.add(s[j:k])
    if len(substr) >= K:
        substr = sorted(list(substr))
        break

print(substr[K-1])
### BUGGY CODE ###

import numpy as np
from itertools import permutations


def warshall_floyd(n, d):
    for i in np.arange(n):
        for j in np.arange(n):
            for k in np.arange(n):
                t = d[j, i] + d[i, k]
                if t < d[j, k]:
                    d[j, k] = t


N, M, R = np.fromstring(input(), dtype = np.int64, sep = ' ')
r = np.fromstring(input(), dtype = np.int64, sep = ' ')

d = np.full((N + 1, N + 1), 1000000000, dtype=np.int64)
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A, B] = C
    d[B, A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i], p[i + 1]]
    result = min(result, t)
print(result)


### FIXED CODE ###

from itertools import permutations


def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


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

d = [[1000000000] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i]][p[i + 1]]
    result = min(result, t)
print(result)
### BUGGY CODE ###

s = input()
snum = list(map(int, input().split()))
q = input()
qnum = list(map(int, input().split()))
c = 0
for i in qnum:
    if i in snum:
        c += 1

print(c)

### FIXED CODE ###

s = input()
snum = set(map(int, input().split()))
q = input()
qnum = list(map(int, input().split()))
c = 0
for i in qnum:
    if i in snum:
        c += 1

print(c)
### BUGGY CODE ###

k = int(input())
s = input()
n = len(s)
#nCk(mod p)を求める
def comb(n, k, p):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    a, b, c = 1, 1, 1
    for i in range(1, n+1):
        a = (a*i)%p
    for i in range(1, k+1):
        b = (b*i)%p
    for i in range(1, n-k+1):
        c = (c*i)%p
    return a*pow(b, p-2, p)*pow(c, p-2, p)%p
mod = 10**9+7
ans = 0
for i in range(k+1):
    pls = pow(25, i, mod)
    pls *= pow(26,k-i, mod)
    pls *= comb(i+n-1, i, mod)
    ans += pls
print(ans%mod)

### FIXED CODE ###

MAX = 10**6 * 3
MOD = 10**9+7
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
#前処理 逆元テーブルを作る
def COMinit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD//i)%MOD
        finv[i] = finv[i-1] * inv[i] % MOD
#実行
def COM(n, k):
    if n  < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
k = int(input())
s = input()
n = len(s)
COMinit()
ans = 0
for i in range(k+1):
    pls = pow(25, i, MOD)
    pls *= pow(26,k-i, MOD)
    pls %= MOD
    pls *= COM(i+n-1, i)
    ans += pls
    ans %= MOD
print(ans%MOD)
### BUGGY CODE ###

S = input()
Q = int(input())
ans = S
revers_count = 0

for i in range(Q):
    Q_i = list(input().split())
    if Q_i[0] == "1":
        revers_count += 1
    else:
        if (Q_i[1] == "1" and revers_count % 2 == 0) or (Q_i[1] == "2" and revers_count % 2 == 1):
            ans = Q_i[2] + ans
        else:
            ans = ans + Q_i[2]

if revers_count % 2 == 1:
    ans = ans[::-1]

print(ans)


### FIXED CODE ###

S = input()
Q = int(input())
revers_count = 0
mae = ""
ushiro = ""

for i in range(Q):
    Q_i = list(input().split())
    if Q_i[0] == "1":
        revers_count += 1
    else:
        if (Q_i[1] == "1" and revers_count % 2 == 0) or (Q_i[1] == "2" and revers_count % 2 == 1):
            mae = Q_i[2] + mae
        else:
            ushiro = ushiro + Q_i[2]

ans = mae + S + ushiro

if revers_count % 2 == 1:
    ans = ans[::-1]

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

R, G, B, N = (int(i) for i in input().split())

c = 0
for r in range(N//R, -1, -1): 
    new1 = N - r*R
    for g in range(new1//G, -1, -1):
        new2 = new1 - g*G
        for b in range(new2//B, -1, -1):
            if b*B == new2:
                c += 1

print(c)

### FIXED CODE ###

R, G, B, N = (int(i) for i in input().split())

c = 0
for r in range(N//R, -1, -1): 
    new1 = N - r*R
    for g in range(new1//G, -1, -1):
        new2 = new1 - g*G
        if new2%B == 0:
            c +=1
    
print(c)