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

import itertools
n, y = map(int, input().split())

sihei = [1000, 5000, 10000]
money = list(itertools.combinations_with_replacement(sihei, n))
flag = False

for i in range(len(money)):
    if sum(money[i]) == y:
        # print(money[i])
        print(str(money[i].count(10000)) + ' ' + str(money[i].count(5000)) + ' ' + str(money[i].count(1000)))
        flag = True
        break

if flag is False:
    print('-1 -1 -1')

### FIXED CODE ###

n, t = map(int, input().split())
flag = False
for x in range(n+1):
    if flag is True:
        break
    for y in range(n-x+1):
        # print(10000 * x + 5000 * y + 1000 * (n-x-y))
        if (10000 * x + 5000 * y + 1000 * (n-x-y)) == t:
            print(str(x) + ' ' + str(y) + ' ' + str(n-x-y))
            flag = True
            break

if flag is False:
    print('-1 ' * 3)
### BUGGY CODE ###

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def multiple(a, b):
    return a*b // euclid(a, b)
import functools
def lcm(nums):
        return functools.reduce(multiple, nums)%mod
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7
ans =0
for i in range(n):
  ans += lcm(num)*modinv(num[i],mod)
  ans %= mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

import fractions
lc = num[0]
for i in range(1, n):
    lc = lc * num[i] // fractions.gcd(lc, num[i])

lc %= mod    
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

ans =0
for i in range(n):
  ans += lc*modinv(num[i],mod)
  ans %= mod
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())
    r = s
    hanten = False
    for i in range(q):
        query = input().split()
        if query[0] == "1":
            s,r = r,s
            hanten = not hanten
        else:
            if query[1] == "1":
                s = query[2] + s
                r = r + query[2]
            if query[1] == "2":
                s = s + query[2]
                r = query[2] + r
    if hanten:
        answer = ""
        for i in range(len(r)-1,-1,-1):
            answer = answer + r[i]
    else:
        answer = s
    print(answer)



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    q = int(input())
    left = ""
    right = ""
    hanten = False
    for i in range(q):
        query = input().split()
        if query[0] == "1":
            hanten = not hanten
        else:
            c = query[2]
            if query[1] == "1":
                if not hanten:
                    left += c
                else:
                    right += c
            else:
                if not hanten:
                    right += c
                else:
                    left += c
        #print(query)
        #print(s,left,right)
    left = left[::-1]
    answer = left + s + right

    if not hanten:
        print(answer)
    else:
        print(answer[::-1])


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

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i+1
xy.sort()

# x<xi,y<yi
l1 = [0]*N
# x<xi,y>yi
l2 = [0]*N
# x>xi,y<yi
r1 = [0]*N
# x>xi,y>yi
r2 = [0]*N

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1[i] = bit.sum(xy[i][1])
    l2[i] = i-l1[i]
    r1[i] = xy[i][1]-l1[i]-1
    r2[i] = N-xy[i][1]-l2[i]
    bit.add(xy[i][1],1)
    ans += (pow2[l2[i]]-1)*(pow2[r1[i]]-1)*pow2[r2[i]]*pow2[l1[i]]
    ans += (pow2[r2[i]]-1)*(pow2[l1[i]]-1)*(pow2[l2[i]]+pow2[r1[i]]-1)
    ans %= mod

print(ans)

### FIXED CODE ###

from operator import itemgetter

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

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

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].append(a)

D = [0] * (n+1)
P = [0] * (n+1)

def dfs(p, i, depth):
    if depth > D[i]:
        D[i] = depth
        P[i] = p
    for t in T[i]:
        dfs(i, t, depth+1)

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

dfs(0, root(1), 1)
for p in P[1:]:
    print(p)

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [set() for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].add(a)

D = [0] * (n+1)
P = [0] * (n+1)
used = [0] * (n+1)

def dfs(p, i, depth):
    if used[i]:
        return None
    D[i] = depth
    P[i] = p
    used[i] = True
    for t in tuple(T[i]):
        RT[t].remove(i)
    for t in tuple(T[i]):
        if not RT[t]:
            dfs(i, t, depth+1)

def root(i):
    if not RT[i]:
        return i
    return root(tuple(RT[i])[0])

dfs(0, root(1), 1)
for p in P[1:]:
    print(p)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
j = 0
d = 0
c0 = 0
l = sorted(list(set(a)))
for i in l:
    if i == j+1:
        j = i
        if i in a[c0:]:
            for k in range(len(a[c0:])):
                if i == a[c0:][k]:
                    p=k
                    break
            c = p+(n-len(a[c0:]))
        else:break
        if c >= c0:
            d += 1
            c0 = c
        else:break
    else:break
print(n-d if d !=0 else -1)

### FIXED CODE ###

from collections import deque
n = int(input())
a = list(map(int, input().split()))
a = deque(a)
d = 0
i = 1
for _ in range(n):
    b = a.popleft()
    if i == b:
        d +=1
        i += 1
        
print(n-d if d !=0 else -1)
### BUGGY CODE ###

#D - Chat in a Circle
N = int(input())
A = list(map(int,input().split()))
#ソート
B = []
B = sorted(A,reverse = True)
Chat = []
Friend_min = 0
Friend_min_max = 0
Friend_min_max_wa = 0
max_no = 0
i =0
Chat.append(B[0])
for i in range(N):
    for j in range(i):
        if (Chat[j] > Chat[j+1]):
            Friend_min = Chat[j+1]
        else:
            Friend_min = Chat[j]
        if Friend_min >= Friend_min_max:
            Friend_min_max = Friend_min
            max_no = j + 1
        Friend_min = 0
    Chat.insert(max_no,B[i])
    Friend_min_max_wa = Friend_min_max_wa + Friend_min_max
    Friend_min_max = 0
    max_no = 0
#    print(Chat)    
# 出力
print(Friend_min_max_wa)

### FIXED CODE ###

#D - Chat in a Circle
N = int(input())
A = list(map(int,input().split()))
#ソート
arr = []
arr = sorted(A,reverse = True)

Friend_min_max_wa = 0
i =0
j = 0
for i in range(N -1):
    if i % 2 != 0 : j = j + 1
    Friend_min_max_wa = Friend_min_max_wa + arr[j]

# 出力
print(Friend_min_max_wa)
### BUGGY CODE ###

f=lambda:map(int,input().split())
N,M=f()
N+=1;V=[-1]*N
Q=list(range(N))
F,B=eval('{i:[]for i in Q},'*2)
exec('x,y=f();F[x]+=[y];B[y]+=[x];'*M)
while Q:
 p=Q.pop();S=[1+V[q]for q in B[p]]
 if all(S)and V[p]<0:V[p]=max(S+[0]);Q+=F[p]
print(max(V))

### FIXED CODE ###

from collections import defaultdict
debug = print
def debug(*va): pass

def longest_by_topological_sort(N, nexts, prevs):
    visited = [-1] * N
    max_dist = 0
    que = list(range(N))
    while len(que):
        p = que.pop()
        if visited[p] == -1:
            if all(visited[q] != -1 for q in prevs[p]):
                dist = 0
                for q in prevs[p]:
                    dist = max(dist, visited[q] + 1)
                visited[p] = dist
                max_dist = max(max_dist, dist)
                for n in nexts[p]:
                    que.append(n)
    return max_dist

def test_separate():
    import time
    N = 10**5
    t0 = time.time()
    print(longest_by_topological_sort(N, defaultdict(list), defaultdict(list)))
    print('elapsed', time.time() - t0)

def test_fanout():
    import time
    N = 10**5
    nn, pp = defaultdict(list), defaultdict(list)
    for i in range(1, N):
        nn[0].append(i)
        pp[i].append(0)
    t0 = time.time()
    print(longest_by_topological_sort(N, nn, pp))
    print('elapsed', time.time() - t0)

def test_middle():
    import time
    N = 10**5
    nn, pp = defaultdict(list), defaultdict(list)
    for i in range(1, N):
        # fanout
        nn[0].append(i)
        pp[i].append(0)
        # fanin
        nn[i].append(1)
        pp[1].append(i)
    t0 = time.time()
    print(longest_by_topological_sort(N, nn, pp))
    print('elapsed', time.time() - t0)

if __name__ == '__main__':
    N, M = map(int, input().split())

    nextnodes = [defaultdict(list), defaultdict(list)]
    for i in range(M):
        x, y = map(int, input().split())
        nextnodes[0][x - 1].append(y - 1)
        nextnodes[1][y - 1].append(x - 1)

    max_dist = longest_by_topological_sort(N, nextnodes[0], nextnodes[1])
    print(max_dist)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
from bisect import bisect_right
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([max(0, S - X), X, 0, i])
    Stop.append([max(0, T - X), X, 1, i])
Stop.sort(key=itemgetter(0, 2))
q = []
notClosed = [False]*N
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, time, idx))
    else:
        notClosed[idx] = True
        while len(q)>0 and notClosed[q[0][2]]:
            aaa = heapq.heappop(q)[2]
            #notClosed[aaa]

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))
assert len(q)==0
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A, (D, 1<<60))

    print(A[idx-1][1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
from bisect import bisect_right
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([S - X, X, 0, i])
    Stop.append([T - X, X, 1, i])
Stop.sort(key=itemgetter(0))
q = []
notClosed = [False]*N
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, idx))
    else:
        notClosed[idx] = True
        while len(q)>0 and notClosed[q[0][1]]:
            aaa = heapq.heappop(q)[1]

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))
A0 = list(map(itemgetter(0), A))
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A0, D)

    print(A[idx-1][1])
### BUGGY CODE ###

import math

def is_prime(n):
  if n == 1:
    return False
  if n%2 ==0:
    if n == 2:
      return True
    else:
      return False
  for i in range(3, int(math.sqrt(n)//1)+1, 2):
    if n%i == 0:
      return False
  return True

Q = int(input())
ans = []
for _ in range(Q):
  counter = 0
  l, r = map(int, input().split())
  for odd in range(l, r+1, 2):
    if is_prime(odd) and is_prime((odd+1)/2):
      counter += 1
  ans.append(counter)

for item in ans:
  print(item)

### FIXED CODE ###

import math

def is_prime(x):
  if x <= 0 or x%1 != 0:
    return False
  elif x == 1:
    return False
  elif x == 2:
    return True
  elif x%2 == 0:
    return False
  else:
    for i in range(3, int(math.sqrt(x)//1)+1, 2):
      if x%i == 0:
        return False
    return True

S = [0] * (10**5+1)
for i in range(1, 10**5+1):
  if is_prime(i) and is_prime((i+1)/2):
    S[i] += 1
  S[i] += S[i-1]

Q = int(input())
for _ in range(Q):
  l, r = map(int, input().split())
  print(S[r] - S[l-1])
### BUGGY CODE ###

h, w = map(int, input().split())
data = []
for i in range(h):
    s = input()
    data.append(s)
cnt_l, cnt_r, cnt_u, cnt_d = [[0] * w for _ in range(h)], [[0] * w for _ in range(h)], [[0] * w for _ in range(h)], [[0] * w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if data[i][j] == "#":
            cnt_l[i][j] = 0
        else:
            cnt_l[i][j] = cnt_l[i][j - 1] + 1
    
        if data[i][w - j - 1] == "#":
            cnt_r[i][w - j - 1] = 0
        else:
            if j == 0:
                cnt_r[i][w - j - 1] = 1
            else:
                cnt_r[i][w - j - 1] = cnt_r[i][w - j] + 1

for j in range(w):
    for i in range(h):
        if data[i][j] == "#":
            cnt_u[i][j] = 0
        else:
            cnt_u[i][j] = cnt_u[i - 1][j] + 1

        if data[h - i - 1][j] == "#":
            cnt_d[h - i - 1][j] = 0
        else:
            if i == 0:
                cnt_d[h - i - 1][j] = 1
            else:
                cnt_d[h - i - 1][j] = cnt_d[h - i][j] + 1

ans = 0
for i in range(h):
    for j in range(w):
        total= cnt_l[i][j] + cnt_r[i][j] + cnt_u[i][j] + cnt_d[i][j] - 3
        ans = max(ans, total)

print(ans)

### FIXED CODE ###

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

cnt_l, cnt_r, cnt_u, cnt_d = [[0] * w for _ in range(h)], [[0] * w for _ in range(h)], [[0] * w for _ in range(h)], [[0] * w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if data[i][j] == "#":
            cnt_l[i][j] = 0
        else:
            cnt_l[i][j] = cnt_l[i][j - 1] + 1
    
        if data[i][w - j - 1] == "#":
            cnt_r[i][w - j - 1] = 0
        else:
            if j == 0:
                cnt_r[i][w - j - 1] = 1
            else:
                cnt_r[i][w - j - 1] = cnt_r[i][w - j] + 1

for j in range(w):
    for i in range(h):
        if data[i][j] == "#":
            cnt_u[i][j] = 0
        else:
            cnt_u[i][j] = cnt_u[i - 1][j] + 1

        if data[h - i - 1][j] == "#":
            cnt_d[h - i - 1][j] = 0
        else:
            if i == 0:
                cnt_d[h - i - 1][j] = 1
            else:
                cnt_d[h - i - 1][j] = cnt_d[h - i][j] + 1

ans = 0
for i in range(h):
    for j in range(w):
        total= cnt_l[i][j] + cnt_r[i][j] + cnt_u[i][j] + cnt_d[i][j] - 3
        ans = max(ans, total)

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

n = int(input())
a = input().split()

b = []

for i in a:
    b.append(i)
    b.reverse()

print(" ".join(b))


### FIXED CODE ###

n = 4
a = [1, 2, 3, 4]

n = int(input())
a = input().split()


if n % 2 == 0:
    y = [a[j] for j in range(1, n, 2)][::-1]
    z = [a[j] for j in range(0, n, 2)]

else:
    y = [a[j] for j in range(0, n, 2)][::-1]
    z = [a[j] for j in range(1, n, 2)]

print(" ".join(map(str, y + z)))
### BUGGY CODE ###

def foo(x,y,z):
    return x**2 + y**2 + z**2 + x*y + y*z + z*x

N = int(input())

for i in range(1,N+1):
    F = [(a,b,c) for a in range(1,N//6+1) for b in range(1,N//6+1) for c in range(1,N//6+1) if foo(a,b,c)==i]
    print(len(F))


### FIXED CODE ###

def foo(x,y,z):
    return x**2 + y**2 + z**2 + x*y + y*z + z*x

N = int(input())

A = [0 for i in range(10050)]

for i in range(1,105):
    for j in range(1,105):
        for k in range(1,105):
            tmp = foo(i,j,k)
            if tmp < 10050:
                A[tmp] += 1

for i in range(1,N+1):
    print(A[i])
### BUGGY CODE ###

N,K,Q = map(int, input().split())
 
A = []
 
for _ in range(Q):
    A.append(int(input()))
	
P = [K] * N
 
r = 0
 
for i in range(0,len(A)):
	r = A[i] - 1
	P[r] += 1
	P = list(map(lambda x: x-1,P))
	
for i in range(0,len(P)):
	if P[i] > 0:
		print("Yes")
	else:print("No")

### FIXED CODE ###

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

P = [0] * N


for i in range(Q):
	A = int(input())
	P[A-1] += 1


for j in range(0,len(P)):
	if K - Q + P[j] > 0:
		print('Yes')
	else:
		print('No')
### BUGGY CODE ###

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

for i in range(N):
  P[i] -= 1

ans = max(C)
S = set(range(N))
while S:
  scores = []
  x = S.pop()
  while True:
    scores.append(C[x])
    x = P[x]
    if x not in S:
      break
    S.remove(x)
  l = len(scores)
  if K <= l:
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = 0
      for k in range(K):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)
  else:
    t = sum(scores)
    t = t * (K // l - 1) if t > 0 else 0
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = t
      for k in range(l + (K%l)):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)

print(ans)

### FIXED CODE ###

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

for i in range(N):
  P[i] -= 1

ans = max(C)
S = set(range(N))
while S:
  scores = []
  x = S.pop()
  while True:
    scores.append(C[x])
    x = P[x]
    if x not in S:
      break
    S.remove(x)
  l = len(scores)
  if K <= l:
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = 0
      for k in range(K):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)
  else:
    t = sum(scores)
    if t < 0:
      t = 0
    q, r = divmod(K, l)
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = t * (q - 1)
      for k in range(l):
        ss += scores[(i+k)%l]
        ans = max(ans, ss + (t if k < r else 0))

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

n,k,q=map(int,input().split())
a=[int(input())-1 for i in range(q)]
ans=[k-q]*n
for i in range(n):
    ans[i]+=a.count(i)
    print("Yes" if ans[i]>0 else "No")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[int(input())-1 for i in range(q)]
ans=[k-q]*n
for i in a:
    ans[i]+=1
for i in range(n):
    print("Yes" if ans[i]>0 else "No")
### BUGGY CODE ###

S=input()
x=0
M=13
MOD=10**9+7
dp=[[0]*M for i in range(2)]
dp[0][0]=1
p=0
for i in range(len(S)):
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[p%2]):
        dp[(p+1)%2][(10*j+s)%M]+=d
  else:
    s=int(s)
    for j,d in enumerate(dp[p%2]):
      dp[(p+1)%2][(10*j+s)%M]=d
  dp[p%2]=[0]*13
  p+=1
  p%=2
print(dp[p%2][5]%MOD)

### FIXED CODE ###

S=input()
import numpy as np
M=13
MOD=10**9+7
dp=np.zeros(M, dtype=np.int64)
dp[0]=1
idx = np.zeros(M, dtype=np.int8)
window = np.ones(10, dtype=np.int8)
for i in range(M):
  idx[i * 10 % M] = i
for s in S:
  if s=='?':
    tdp=dp[idx]
    ndp = np.concatenate([tdp[4:], tdp])
    dp = np.convolve(ndp, window, mode='valid') % MOD
  else:
    dp=np.roll(dp[idx],int(s))
print(dp[5]%MOD)
### BUGGY CODE ###

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

for i in range(m):
    j = 0
    for j in range(n):
        if lm[i] == ln[j]:
            del ln[j]
            n -= 1
            break
        elif lm[i] < ln[j] or lm[i] > ln[n-1]:
            print("NO")
            exit()

print("YES")

### FIXED CODE ###

import sys
from collections import Counter
 
N = int(input())
s1 = list(map(int,input().split()))
M = int(input())
s2 = list(map(int,input().split()))
 
c1 = Counter(s1)
c2 = Counter(s2)
 
for k,v in c2.items():
    if k in c1:
        if v > c1[k]:
            print('NO')
            sys.exit()
    else:
        print('NO')
        sys.exit()
print('YES')
### BUGGY CODE ###

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

fn = lambda: [int(x) for x in input().split()]
N, M, R = fn()
r = [int(ri) - 1 for ri in input().split()]
A, B, C = [0]*M, [0]*M, [0]*M
for i in range(M):
    A[i], B[i], C[i] = fn()
    A[i], B[i] = A[i] - 1, B[i] - 1

G = csr_matrix((C, (A, B)), shape=(N, N), dtype=float)
dist_matrix = G.todense()
dist_matrix[dist_matrix == 0] = float('inf')
dist_matrix.flat[::N + 1] = 0
for i in range(N):
    for j in range(i + 1, N):
        if dist_matrix[j, i] <= dist_matrix[i, j]:
            dist_matrix[i, j] = dist_matrix[j, i]
        else:
            dist_matrix[j, i] = dist_matrix[i, j]
for k in range(N):
    for i in range(N):
        if dist_matrix[i, k] == float('inf'):
            continue
        for j in range(N):
            d_ijk = dist_matrix[i, k] + dist_matrix[k, j]
            if d_ijk < dist_matrix[i, j]:
                dist_matrix[i, j] = d_ijk

D = dist_matrix

# D = floyd_warshall(G, directed=False)

routes = permutations(r)
result = float('inf')
for route in routes:
    d = sum([D[route[i], route[i+1]] for i in range(len(route) - 1)])
    result = min(result, d)
print(int(result))


### FIXED CODE ###

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

fn = lambda: [int(x) for x in input().split()]
N, M, R = fn()
r = [int(ri) - 1 for ri in input().split()]
A, B, C = [0]*M, [0]*M, [0]*M
for i in range(M):
    A[i], B[i], C[i] = fn()
    A[i], B[i] = A[i] - 1, B[i] - 1

G = csr_matrix((C, (A, B)), shape=(N, N), dtype=int)
D = floyd_warshall(G, directed=False)

routes = permutations(r)
result = float('inf')
for route in routes:
    d = sum([D[route[i], route[i+1]] for i in range(len(route) - 1)])
    result = min(result, d)
print(int(result))
### BUGGY CODE ###

# coding:utf-8

import math

def main():
    s = list(raw_input())
    s.reverse()
    cnt = 0
    total = 0
    while True:
        chk = False
        for i in s:
            if i == 'C' and cnt < len(s) - 2:
                if s[cnt+1] == 'B' and s[cnt+2] == 'A':
                    s[cnt] = 'A'
                    s[cnt+1] = 'C'
                    s[cnt+2] = 'B'
                    total += 1
                    chk = True
                    break
            cnt += 1
        if chk == True:
            cnt = 0
            continue
        else:
            break
    print total


if __name__ == "__main__":
    main()



### FIXED CODE ###

# coding:utf-8

import math

def main():
    s = list(raw_input())
    substr = ''
    total = []
    cnt = 0
    m = False
    for i in s:
        if i == 'A' and m == False:
            cnt += 1
        elif i == 'A':
            cnt = 1
            m = False
        elif i == 'B' and m == False:
            m = True
        elif i == 'C' and m == True:
            total.append(cnt)
            m = False
        else:
            m = False
            cnt = 0
    result = 0
    for i in total:
        result += i
    print result

if __name__ == "__main__":
    main()