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

from collections import deque
H,W=map(int,input().split())

l=[input() for _ in range(H)]


def bfs(H,W,l):
  ans=0
  que=deque()
  count=[[-1]*W for _ in range(H)]
  num=H*W
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  for i in range(H):
    for j in range(W):
      if l[i][j]=='#':
        count[i][j]=0
        que.append([i,j])
        num-=1
  while num>0:
    x,y=que.popleft()
    for k in range(4):
      a, b=x+dx[k], y+dy[k]
      if a<0 or a>=H or b<0 or b>=W or count[a][b]!=-1:
        continue
      else:
        count[a][b]=count[x][y]+1
        que.append([a,b])
        num-=1
  for i in range(H):
    ans=max(ans,max(count[i]))
  return ans
print(bfs(H,W,l))
    

### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())

l=[input() for _ in range(H)]


def bfs(H,W,l):
  ans=0
  que=deque()
  count=[[-1]*W for _ in range(H)]
  num=H*W
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  for i in range(H):
    for j in range(W):
      if l[i][j]=='#':
        count[i][j]=0
        que.append([i,j])
        num-=1
  while num>0:
    x,y=que.popleft()
    for k in range(4):
      a, b=x+dx[k], y+dy[k]
      if a<0 or a>=H or b<0 or b>=W or count[a][b]!=-1:
        continue
      else:
        count[a][b]=count[x][y]+1
        que.append([a,b])
        num-=1
  for i in range(H):
    ans=max(ans,max(count[i]))
  return ans
print(bfs(H,W,l))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = [[] for _ in range(n)]
M = iter(pqc)

#s = [set() for _ in range(n)]
s = set()
for p,q,c in zip(M,M,M):
    p -= 1
    q -= 1
    g[p].append((q,c))
    g[q].append((p,c))
    if p==0 or q==0: s.add(c)
    #s[p].add(c)
    #s[q].add(c)
    


from collections import deque
def bfs01(g,s):
    n = len(g)
    #checked = [0]*n
    #checked[0] = 1
    ans = INF = 1<<30
    mask = (1<<20)-1
    q = deque((ci,1) for ci in s)
    res = {ci:1 for ci in s}
    
    mmm = [INF]*n
    
    #print(res)
    while q:
        vl,dv = q.popleft()
        v,l = vl>>20, vl&mask
        if res[vl] < dv or mmm[v] < dv: continue
        for to,line in g[v]:
            tl = (to<<20)+line
            ndv = dv+(0 if l==line else 1)
            if tl not in res or res[tl] > ndv and mmm[to] >= ndv:
                mmm[to] = min(mmm[to],ndv)
                res[tl] = ndv
                if l==line: q.appendleft((tl,ndv))
                else: q.append((tl,ndv))
                
                #if to == n-1: ans = min(ans,ndv)
                
                #print(tl,ndv,(v,l,dv),l==line)
    ans = mmm[-1]                
        #print(q)
    if ans==INF: ans=-1
    return ans



print(bfs01(g,s))


#print(res)




### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int,input().split())) for _ in range(q)]

sum = sum(a)

for i in bc:
    b = i[0]
    c = i[1]
    count = a.count(b)
    a = [c if i==b else i for i in a]
    sum += count*(c-b)
    # print(a)
    print(sum)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
query = [list(map(int,input().split())) for _ in range(q)]

all_sum  = sum(a)

cnt = {}
for i in a:
    if i not in cnt:
        cnt[i] = 0
    cnt[i] += 1

for (b, c) in query:
    if b in cnt:
        all_sum -= b * cnt[b]
        all_sum += c * cnt[b]
        if c not in cnt:
            cnt[c]=0 
        cnt[c] += cnt[b]
        cnt[b] = 0
    print(all_sum)
### BUGGY CODE ###

num = input().split(' ')
num_data = [int(num[i]) for i in range(3)]
#N X Y
cost = [0 for i in range(num_data[0] - 1)] #start position has the lowest number
for i in range(num_data[0] - 1):
    for l in range(num_data[0] - i - 1):
        result = min(abs(i - l - i - 1),abs(i - num_data[1] + 1) + 1 + abs(l + i + 1 - num_data[2] + 1),abs(i - num_data[2] + 1) + 1 + abs(l + i + 1 - num_data[1] + 1))
        cost[int(result) - 1] += 1
for per in cost:
    print(per)


### FIXED CODE ###

def main():
    n,x,y = map(int,input().split(' '))
    cost = [0 for i in range(n - 1)]
    for i in range(n - 1):
        for l in range(i + 1, n):
            result = min(abs(i - l),abs(i - x + 1) + 1 + abs(l - y + 1),abs(i - y + 1) + 1 + abs(l - x + 1))
            cost[result - 1] += 1
    for per in cost:
        print(per)

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

n = int(input())
s = input()

ans = 0
for i in range(1000):
    flag = [False, False, False]
    st = str(i).zfill(3)
    for j in range(len(s)):
        if st[0] == s[j] and not flag[0] and not flag[1]:
            flag[0] = True
        elif st[1] == s[j] and flag[0] and not flag[1]:
            flag[1] = True
        elif st[2] == s[j] and flag[0] and flag[1]:
            flag[2] = True
        if all(flag):
            ans += 1
            break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = 0
for i in range(1000):
    flag = [False, False, False]
    st = str(i).zfill(3)
    a = s.find(st[0])
    if a != -1:
        b = s.find(st[1],a+1)
        if b != -1:
            c =s.find(st[2],b+1)
            if c != -1:
                ans += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))



def main():
    count = 0
    A,B,C = inpl()
    K = int(input())
    while True:
        if A < B < C:
            print('Yes')
            return
        if B < A:
            B *= 2
            count += 1
            if count == K and not(A < B < C):
                print('No')
                return
        if C < B:
            C *= 2
            count += 1
            if count == K and not(A < B < C):
                print('No')
                return
main()


### FIXED CODE ###

from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))



def main():
    count = 0
    A,B,C = inpl()
    K = int(input())
    for i in range(K+1):
        for j in range(K+1-i):
            k = K-i-j
            a = A*(2**i)
            b = B*(2**j)
            c = C*(2**k)
            if a < b < c:
                print('Yes')
                return

    print('No')
    """while True:
        if A < B < C:
            print('Yes')
            return
        if B < A:
            B *= 2
            count += 1
            if count == K and not(A < B < C):
                print('No')
                return
        if C < B:
            C *= 2
            count += 1
            if count == K and not(A < B < C):
                print('No')
                return"""
main()
### BUGGY CODE ###

H, N = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
limit = H + max(A[i][0] for i in range(N))
dp = [int(1e18) for _ in range(limit+1)]
dp[0] = 0
for i in range(1, limit+1):
  for j in range(N):
    if A[j][0] > i:
      dp[i] = min(dp[i], A[j][1])
    else:
      dp[i] = min(dp[i], dp[i-A[j][0]]+A[j][1])
M = min(dp[i] for i in range(H, limit+1))
print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
limit = H + max(A[i][0] for i in range(N))
dp = [int(1e18) for _ in range(limit+1)]
dp[0] = 0
for i in range(1, limit+1):
  for j in range(N):
    if A[j][0] > i:
      dp[i] = min(dp[i], A[j][1])
    else:
      dp[i] = min(dp[i], dp[i-A[j][0]]+A[j][1])
M = min(dp[i] for i in range(H, limit+1))
print(dp[H])
### BUGGY CODE ###

a = int(input())
num_list = list(map(int, input().split()))
ori_list = set(num_list)
for i in range(a):
    if i+1 in ori_list:
        print(num_list.count(i+1))
    else:
        print(0)

### FIXED CODE ###


from collections import Counter
a = int(input())
num_list = list(map(int, input().split()))
D = Counter(num_list)
for i in range(a):
    print(D[i+1])
### BUGGY CODE ###

# import sys
import math #sqrt,gcd
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
from itertools import product,permutations,combinations,combinations_with_replacement #順列生成
# import collections # deque
from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    s = input()
    ans = 0
    for x in combinations(range(n),3):
        i,j,k = x
        if j-i==k-j: continue
        if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
            ans += 1
    print(ans)
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    s = input()
    rgb = {"R":0,"G":0,"B":0}
    for i in s:
        rgb[i] += 1
    ans = 1
    for i in rgb.keys():
        ans *= rgb[i]
    for i in range(n-2):
        for j in range(i+1,n-1):
            k = j + (j-i)
            if k>=n:
                continue
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                ans -= 1
    print(ans)
    return

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

INF = float('inf')
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [0] * (N+1)
b = [0] * (M+1)
for i,x in enumerate(A):
    a[i+1] = a[i] + x

for i,x in enumerate(B):
    b[i+1] = b[i] + x

ans = 0
for i, va in enumerate(a):
    j = M
    while j >= 0:
        if va + b[j] > K:
            j -= 1
            continue
        ans = max(i+j, ans)
        j -= 1
print(ans)


### FIXED CODE ###

INF = float('inf')
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [0] * (N+1)
b = [0] * (M+1)
for i,x in enumerate(A):
    a[i+1] = a[i] + x

for i,x in enumerate(B):
    b[i+1] = b[i] + x

ans = 0
j = M
for i, va in enumerate(a):
    if va > K:
        break
    while va + b[j] > K:
        #print(va, b[j], ans)
        j -= 1
        if j < 0:
            break
    ans = max(i+j, ans)
print(ans)
### BUGGY CODE ###

n,m,k=map(int,input().split())
fr=[input() for i in range(m)]
bl=[input() for i in range(k)]
relfr=[set() for i in range(n)]
relbl=[set() for i in range(n)]
for l in fr:
  a,b=map(int,l.split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for l in bl:
  a,b=map(int,l.split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
cand=[0]
searched=set()
gr=set()
all_gr={i for i in range(n)}
ans=['']*n
while all_gr!=searched:
  while len(cand)!=0:
    now=cand.pop()
    gr.add(now)
    for point in relfr[now]-(relfr[now]&gr)-(relfr[now]&set(cand)):
      if not point in gr and not point in cand:
        cand.append(point)
  for i in gr:
    ans[i]=str(len(gr)-len(relfr[i])-len(relbl[i]&gr)-1)
    searched.add(i)
  gr.clear()
  if all_gr!=searched:
    cand.append(list(all_gr-searched)[0])
print(' '.join(ans))

### FIXED CODE ###

n,m,k=map(int,input().split())
relfr={i:set() for i in range(n)}
relbl={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for i in range(k):
  a,b=map(int,input().split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
blsiz=[0 for i in range(n)]
ans=[0]*n
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
uf=UnionFind(n)
for i in range(n):
  for j in relfr[i]:
    uf.Unite(i,j)
for i in range(n):
  for j in relbl[i]:
    if uf.isSameGroup(i,j):
      blsiz[i]+=1
for i in range(n):
  ans[i]=uf.Count(i)-len(relfr[i])-blsiz[i]-1

print(' '.join(map(str,ans)))
### BUGGY CODE ###

N= int(input())
# queryを投げて空の時の処理をする関数
def query(i):
  print(i)
  tmp = input()
  if tmp == 'Vacant':
    exit()
  else:
    return r

# 最初に始点を探索
z = query(0)
  
# 矛盾していないか判定する関数, Falseなら矛盾
def judge(m):
  s = query(m)
  if m % 2 == 0: # 偶数なら0番目と同じなら矛盾しない
    return z == s
  else:
    return z != s
  
# 二分探索する
l = 0
r = N # N-1にするとN-1が探索されずにwhileを抜けてしまう
while r - l > 1:
  m = (l + r) // 2
  if judge(m):
    # l~mまでが矛盾しない
    l = m
  else:
    r = m

### FIXED CODE ###

N= int(input())

# queryを投げて空の時の処理をする関数
def query1(i):
  print(i)
  tmp = input()
  if tmp[0] == 'V':
    exit()
  return tmp

# 最初に始点を探索
z = query1(0)
  
# 矛盾していないか判定する関数, Falseなら矛盾
def judge1(m):
  s = query1(m)
  if m % 2 == 0: # 偶数なら0番目と同じなら矛盾しない
    return z==s
  else:
    return z!=s
  
# 二分探索する
l = 0
r = N # N-1にするとN-1が探索されずにwhileを抜けてしまう
while r - l > 1:
  m = (l + r) // 2
  if judge1(m):
    # l~mまでが矛盾しない
    l = m
  else:
    r = m
### BUGGY CODE ###

def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b);

n, start = [int(a) for a in input().split()]
x = [int(b) for b in input().split()]
x = x + [start]
x = [c - min(x) for c in x]
DifferenceList = list()
for i, v in enumerate(x):
    if (i > 0):
        DifferenceList.append(abs(x[i] - x[i - 1]))

g = DifferenceList[0]
for d in DifferenceList:
    g = gcd(g, d)

print (g)

### FIXED CODE ###

def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b);

n, start = [int(a) for a in input().split()]
x = [int(b) for b in input().split()]
x = x + [start]
mi = min(x)

g = abs((x[1] - mi) - (x[0] - mi))
for i, v in enumerate(x):
    if (i > 0):
        d = abs((x[i] - mi) - (x[i - 1] - mi))
        g = gcd(g, d)
        
print (g)
### BUGGY CODE ###

def simple_solution(N, A, B):
    ret = 0
    for a in A:
        for b in B:
            ret ^= a + b
    return ret


def solution(N, A, B):
    import bisect
    pow_2_k = 1
    ans = 0
    for k in range(30):
        MA = [a % (2 * pow_2_k) for a in A]
        MB = [b % (2 * pow_2_k) for b in B]
        MB.sort()
        # [2**k, 2 * (2**k)) か [3 * (2**k), 4 * (2**k)) の中に入るとk-bit目が1。
        # この a + b の数をカウントする。
        # → [2**k - a, 2 * (2**k) - a) か [3 * (2**k) - a, 4 * (2**k) - a) の中に入る b の数をカウント。
        cnt = 0
        for a in MA:
            index_1 = bisect.bisect_left(MB, pow_2_k - a)
            index_2 = bisect.bisect_left(MB, 2 * pow_2_k - a)
            index_3 = bisect.bisect_left(MB, 3 * pow_2_k - a)
            cnt += (N - index_1) - (N - index_2) + (N - index_3)
        if cnt % 2 == 1:
            ans += pow_2_k
        pow_2_k *= 2
    return ans


def check():
    import random
    random.seed(0)
    for N in range(1, 101):
        A = random.choices(range(2 ** 28), k=N)
        B = random.choices(range(2 ** 28), k=N)
        print('Checking the case with size: {}'.format(N))
        assert simple_solution(N, A, B) == solution(N, A, B)
    print('OK')


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    print(solution(N, A, B))


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


### FIXED CODE ###

import numpy as np


def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    B = np.array(list(map(int, input().split())))
    pow_2_k = 1
    ans = 0
    for k in range(30):
        MA = A % (2 * pow_2_k)
        MB = B % (2 * pow_2_k)
        MB.sort()
        # [2**k, 2 * (2**k)) か [3 * (2**k), 4 * (2**k)) の中に入るとk-bit目が1。
        # この a + b の数をカウントする。
        # → [2**k - a, 2 * (2**k) - a) か [3 * (2**k) - a, 4 * (2**k) - a) の中に入る b の数をカウント。
        cnt = 0
        indices_1 = np.searchsorted(MB, pow_2_k - MA, side='left')
        indices_2 = np.searchsorted(MB, 2 * pow_2_k - MA, side='left')
        indices_3 = np.searchsorted(MB, 3 * pow_2_k - MA, side='left')
        cnt += ((N - indices_1) - (N - indices_2) + (N - indices_3)).sum()
        if cnt % 2 == 1:
            ans += pow_2_k
        pow_2_k *= 2
    print(ans)


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

N = int(input())
D = list(map(int, input().split()))
mod = 998244353
counter = [0] * N
for d in D:
    counter[d] += 1

if counter[0] != 1:
    print(0)
    exit()

ans = 1
for d in D[1:]:
    ans *= counter[d-1] % mod
print(ans % mod)

### FIXED CODE ###

N = int(input())
D = list(map(int, input().split()))
mod = 998244353
counter = [0] * N
for d in D:
    counter[d] += 1

if counter[0] != 1:
    print(0)
    exit()

ans = 1
for d in D[1:]:
    ans = ans * counter[d-1] % mod
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
Q = [ list(input().split()) for _ in range(q) ]

count = 0
for i in range(q):
    t = int(Q[i][0])
    if t==1:
        count += 1
    else:
        f = int(Q[i][1])
        if count%2==0 and f==1:
            s = Q[i][2] + s
        elif count%2==0 and f==2:
            s = s + Q[i][2]
        elif count%2==1 and f==1:
            s = s + Q[i][2]
        elif count%2==1 and f==2:
            s = Q[i][2] + s
        else:
            pass

# print(count)

if count%2==0:
    print(s)
    exit()
else:
    s = s[::-1]
    print(s)
    exit()

### FIXED CODE ###

s = input()
q = int(input())
Q = [ list(input().split()) for _ in range(q) ]

from collections import deque
s = deque(list(s))

count = 0
for i in range(q):
    t = int(Q[i][0])
    if t==1:
        count += 1
    else:
        f = int(Q[i][1])
        new = Q[i][2]
        if count%2==0 and f==1:
            s.appendleft(new)
        elif count%2==0 and f==2:
            s.append(new)
        elif count%2==1 and f==1:
            s.append(new)
        elif count%2==1 and f==2:
            s.appendleft(new)
        else:
            pass

# print(count)

if count%2==0:
    print("".join(s))
    exit()
else:
    s = list(s)[::-1]
    print("".join(s))
    exit()
### BUGGY CODE ###

def permutation(lst):
    if len(lst) < 2:
        return[lst]
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remLst = lst[:i] + lst[i+1:]
        for p in permutation(remLst):
            l.append([m] + p)
    return l

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[-1 for x in range(N+1)] for x in range(N+1)]

for i in range(M):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C

##dist = [[(2 * (10 ** 8)) for x in range(N+1)] for x in range(N+1)]
#FloydWarshall
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]
                
rpsec = permutation(rseq)
minimum = 200000000
for p in rpsec:
    total = 0
    for j in range(1,R):
        total += graph[p[j]][p[j-1]]
    if total < minimum:
        minimum = total
print(minimum)





### FIXED CODE ###

from itertools import permutations
 
 
def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist
 
 
def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d
 
    warshallFloyd(N+1, dp)
 
    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)
 
 
if __name__ == '__main__':
    main()