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

import sys
sys.setrecursionlimit(10**7)
from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)


### FIXED CODE ###

from subprocess import call
call(('pypy3','-c',"""
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
m=[[-1]*W for i in range(H)]

from collections import deque
q=deque()
for y in range(H):
  for x in range(W):
    if A[y][x]=='#':
      q.append((y,x))
      m[y][x]=0      
      
def bfs(q,m):
  d=0
  while q:
    y,x=q.popleft()
    d=m[y][x]
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W and m[ny][nx]==-1 and A[ny][nx]!='#':
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1            
bfs(q,m)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,m[i][j])    
print(ans)     
"""))
### BUGGY CODE ###

import copy
import numpy as np
 
n, t = map(int, input().split())
L = np.array([int(i) for i in input().split()])
#LL = L.copy()
#LL = np.sort(LL)

minvalue = L[0]
maxvalue = L[0]
subt = 0
count = 1
flag = 0
for i in range(n-1):
  i = 0
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1

  maxvalue = max(L)
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
#  print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))
  L = L[1:]   
print(count)

### FIXED CODE ###

import copy
 
n, t = map(int, input().split())
L = [int(i) for i in input().split()]

LL = [[0] for i in range(n)]
tmax = L[-1]
for i in range(n):
  if tmax <= L[-i-1]:
    tmax = L[-i-1]
  LL[-i-1] = tmax
 
minvalue = L[0]
maxvalue = LL[0]
subt = 0
count = 1
flag = 0
flagg = 0
j = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  
  maxvalue = LL[i]
 
  #if maxvalue == L[i]:
    #LL = LL[i-j+1:]
    #maxvalue = max(LL)
    #j = i+1
 
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
  #print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))
 
print(count)
### BUGGY CODE ###

mod=10**9+7
N,K=map(int,input().split())
gcd=[0]*(K+1)
ans=0
multipleNumber=0
for i in reversed(range(1,K+1)):
    multipleNumber=K//i
    totalNumber=multipleNumber**N%mod
    minus=range(2*i,K+1,i)
    for j in minus:
        totalNumber-=gcd[j]
        totalNumber%=mod
    gcd[i]=totalNumber
    ans+=i*gcd[i]
print(ans%mod)

### FIXED CODE ###

mod=10**9+7
N,K=map(int,input().split())
d=[0]*(K+1)
ans=0
for i in range(1,K+1):
    d[i]=pow(K//i,N,mod)
for i in range(K,0,-1):
    for j in range(2*i,K+1,i):
        d[i]-=d[j]
        d[i]%=mod
    ans+=d[i]*i
    ans%=mod
print(ans)
### BUGGY CODE ###

import sys

n=0
m=0
id_list=[]

def calculate(x):
  c = len(list(filter(lambda id_list_index: (x >= id_list[id_list_index][0]) and (x <= id_list[id_list_index][1]) , range(0, m))))
  if m == c:
    return True
  return False

is_arg_ok = False
try:
  n, m  = map(int, input().split())
  for i in range(0, m):
    gate_min, gate_max = map(int, input().split())
    id_list.append([gate_min, gate_max])
  is_arg_ok = True
  
except:
  print('arg error')
  sys.exit(1)


result = len(list(filter(lambda x: calculate(x), range(1, n + 1))))
print(result)
sys.exit(0)


### FIXED CODE ###

import sys
n=0
m=0

n, m  = map(int, input().split())
_min, _max  = map(int, input().split())
for i in range(1, m):
  gate_min, gate_max = map(int, input().split())
  if (_max > gate_max):
    _max = gate_max
   
  if _min < gate_min:
    _min = gate_min
 
result_list = list(filter(lambda x : (_min <= x) and (x <= _max), range(1, n+1)))
result = len(result_list)

print(result)
sys.exit(0)
### BUGGY CODE ###

def cns(ls,m,sm):
    global n, s
    count = 0
    if m == n:
        if sm == s: return 1
        else      : return 0
    elif  sm <= s:
        for i in range(9-m+1):
            rls = ls[:]
            k = rls.pop(i)
            count += cns(rls,m+1,sm+(m+1)*k)
        return count
    else: return 0

def mx(i):
    if i <= 0: return 0
    else     : return (i+1)*i + mx(i-1)

ls = [0,1,2,3,4,5,6,7,8,9]
while True:
    n, s = map(int, raw_input().split())
    if s > mx(n): print 0
    else        : print cns(ls,0,0)

### FIXED CODE ###

def mxmn(ls,m):
	global n
	s1,s2 = 0, 0
	for i in range(m):
		s1 += (n-i)*ls[-i-1]
		s2 += (n-i)*ls[i]
	return s1,s2

def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		mx,mn = mxmn(ls,m)
		if mx < s or mn > s: return 0
		elif mx == s or mn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break
### BUGGY CODE ###

def main():
    """"ここに今までのコード"""

    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    count = 0
    while a != []:
        t = a[0]
        if len(a) == 1:
            count +=1
        elif a[0] != a[1]:
            count +=1
        a = [i for i in a if i % t != 0]
    
    print(count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n=int(input())
    A=list(map(int, input().split()))
    counts=[0]*(10**6+5)
    for AA in A:
        counts[AA]+=1
    ans=0
    for i in range(1,10**6+5):
        if counts[i]>0:
            for j in range(i+i,10**6+5,i):
                counts[j]=-1
        if counts[i]==1:
            ans+=1
    print(ans)
        

        
    


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

from collections import deque

H,W = list(map(int,input().split()))
A = [["#"]*(W+2)]
for i in range(H):
    A.append(list("#"+input()+"#"))
A.append(["#"]*(W+2))

queue = deque()
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j] == "#":
            queue.append((i,j,0))

ans = 0
while queue:
    point = queue.popleft()
    ans = max(ans,point[2])
    for y,x in ((1,0),(0,1),(-1,0),(0,-1)):
        if A[point[0]+y][point[1]+x] == ".":
            A[point[0]+y][point[1]+x] = "#"
            queue.append((point[0]+y,point[1]+x,point[2]+1))
print(ans)

### FIXED CODE ###

from collections import deque

def main():
    H,W = list(map(int,input().split()))
    A = [["#"]*(W+2)]
    for i in range(H):
        A.append(list("#"+input()+"#"))
    A.append(["#"]*(W+2))

    queue = deque()
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == "#":
                queue.append((i,j,0))

    ans = 0
    while queue:
        point = queue.popleft()
        ans = max(ans,point[2])
        for y,x in ((1,0),(0,1),(-1,0),(0,-1)):
            if A[point[0]+y][point[1]+x] == ".":
                A[point[0]+y][point[1]+x] = "#"
                queue.append((point[0]+y,point[1]+x,point[2]+1))
    print(ans)

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

N, K = [int(i) for i in map(int, input().split())]
a = list(map(int, input().split()))
dp = []


def mincos(dp, a, i, k):
    if i == 0:
        return 0
    elif i < k:
        mincos = 100000000000
        for j in range(1, i + 1):
            if mincos > dp[i - j] + abs(a[i] - a[i - j]):
                mincos = dp[i - j] + abs(a[i] - a[i - j])
        return mincos
    else:
        mincos = 10000000000
        for j in range(1, k + 1):
            if mincos > dp[i - j] + abs(a[i] - a[i - j]):
                mincos = dp[i - j] + abs(a[i] - a[i - j])
        return mincos


for i in range(N):
    dp.append(mincos(dp, a, i, K))

print(dp[N-1])


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0] * N)

for i in range(1, N):
    j = max(0, i-K)
    dp[i] = (dp[j:i] + np.abs(h[i] - h[j:i])).min()


print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[-1]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    dp = [0] * (W + 1)
    for _ in range(N):
        w, v = map(int, input().split())
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    print(dp[-1])


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())

    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))


main()
### BUGGY CODE ###

S = input()
Q = int(input())

forward = True

for _ in range(Q):
    query = input().split()

    if query[0] == '1':
        forward = not forward

    else:
        head = (query[1] == '1')

        if head ^ forward:
            S = S + query[2]

        else:
            S = query[2] + S

if forward:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())

forward = True
que0 = []
que1 = []

for _ in range(Q):
    query = input().split()

    if query[0] == '1':
        forward = not forward

    else:
        head = (query[1] == '1')
        if head ^ forward:
            que1.append(query[2])
        else:
            que0.append(query[2])

S = ''.join(que0[::-1]) + S + ''.join(que1)

if forward:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))



#複数の最小公倍数
def calc_lcm_list(l):
    lcm = l[0]
    for i in range(1, N):
        lcm = lcm * l[i] // fractions.gcd(lcm, l[i])
    return lcm


import fractions
N = input_one_number()
lstA = input_multiple_number_as_list()

gcd = calc_lcm_list(lstA)

ans = 0
for a in lstA:
    ans += (gcd // a)
    ans %= 1000000007

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)

def calc_gcd_list(l):
    gcd = l[0]
    for i in range(1, N):
        gcd = gcd(gcd, l[i])
    return gcd

def calc_lcm_list(l):
    lcm = 1
    for i in l:
        lcm = lcm * i // gcd(lcm, i)
    return lcm


N = input_one_number()
lstA = input_multiple_number_as_list()
lcm = calc_lcm_list(lstA)
pow = 10**9 +7
print(sum(lcm//a for a in lstA)%pow)
### BUGGY CODE ###

R=lambda: map(int, input().split())

n, m = R()
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = R()
  g[u - 1].append(v - 1)
  g[v - 1].append(u - 1)

r = [None] * (n - 1)
V = [True] + [False] * (n - 1)
q = [0]; s = 0
while q[s:]:
  u = q[s]; s += 1
  for v in g[u]:
    if not V[v]:
      V[v] = True
      r[v - 1] = u + 1
      q.append(v)

print(*(['No'],['Yes'] + r)[all(r)], sep='\n')


### FIXED CODE ###

from collections import deque

R=lambda: map(int, input().split())

n, m = R()
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = R()
  g[u - 1].append(v - 1)
  g[v - 1].append(u - 1)

r = [None] * (n - 1)
V = [True] + [False] * (n - 1)
q = deque([0])
while q:
  u = q.popleft()
  for v in g[u]:
    if not V[v]:
      V[v] = True
      r[v - 1] = u + 1
      q.append(v)

print(*(['No'],['Yes'] + r)[all(r)], sep='\n')
### BUGGY CODE ###

s=str(input())
q=int(input())
a=[input()for i in range(q)]

for i in range(q):

    if a[i]=="1":
        s = ''.join(list(reversed(s)))
    
    else:

        if a[i][2]=="1":
            s=a[i][4]+s

        else:
            s=s+a[i][4]


print(s)


### FIXED CODE ###

s=str(input())
q=int(input())
a=[input()for i in range(q)]
b=0
c=""
d=""
if q<=10**5:
    for i in range(q):
        if a[i]=="1":
            if b==0:
                b=1
            else:
                b=0
        else:
            if b==0:
                if a[i][2]=="1":
                    s=a[i][4]+s
                else:
                    s=s+a[i][4]
            else:
                if a[i][2]=="1":
                    s=s+a[i][4]
                else:
                    s=a[i][4]+s
    if b==0:
        print(s)
    else:
        s= ''.join(list(reversed(s)))
        print(s)

else:
    for i in range(10**5):
        if a[i]=="1":
            if b==0:
                b=1
            else:
                b=0
        else:
            if b==0:
                if a[i][2]=="1":
                    s=a[i][4]+s
                else:
                    s=s+a[i][4]
            else:
                if a[i][2]=="1":
                    s=s+a[i][4]
                else:
                    s=a[i][4]+s
    for i in range(10**5,q):
        if a[i]=="1":
            if b==0:
                b=1
            else:
                b=0
        else:
            if b==0:
                if a[i][2]=="1":
                    c=a[i][4]+c
                else:
                    d=d+a[i][4]
            else:
                if a[i][2]=="1":
                    d=d+a[i][4]
                else:
                    c=a[i][4]+c
    if b==0:
        print(c+s+d)
    else:
        c=''.join(list(reversed(c)))
        d=''.join(list(reversed(d)))
        s= ''.join(list(reversed(s)))
        print(d+s+c)
### BUGGY CODE ###

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

A.sort(reverse=True)

ans = 0

for _ in range(N):
    A.pop(0)
    A.pop()

    ans += A[0]
    A.pop(0)
    
print(ans)

### FIXED CODE ###

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

A.sort()
ans = 0

for i in range(N, 3*N, 2):
    ans += A[i]
    
print(ans)
### BUGGY CODE ###

n=int(input())
a=map(int,input().split())
b=map(int,input().split())
c=map(int,input().split())
a=sorted(a)
b=sorted(b)
c=sorted(c)

import bisect

m=0
for i in a:
    x=bisect.bisect_right(b,i)
    for j in range(x,n):
        y=bisect.bisect_right(c,b[j])
        m+=n-y
print(m)


### FIXED CODE ###

n=int(input())
a=map(int,input().split())
b=map(int,input().split())
c=map(int,input().split())
a=sorted(a)
b=sorted(b)
c=sorted(c)

import bisect

m=0
d=[0 for i in range(n)]
for i in range(n):
    y=bisect.bisect_right(c,b[n-1-i])
    m+=n-y
    d[n-1-i]=m

m=0
for i in a:
    x=bisect.bisect_right(b,i)
    try :
        m+=d[x]
    except IndexError:
        pass
    
print(m)
### BUGGY CODE ###

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


ps = list(map(int, input().split()))
cs = list(map(int, input().split()))

graphs = []
vGraphs = []
flags = [False]*n
for i in range(len(ps)):
    p = ps[i]
    index = p - 1
    if flags[index]:
        continue

    current = set()
    values = set()
    currentIndex = index
    while True:
        if flags[currentIndex]:
            break

        current.add(currentIndex)
        values.add(cs[currentIndex])
        flags[currentIndex] = True
        nextIndex = ps[currentIndex] - 1
        currentIndex = nextIndex
    graphs.append(current)
    vGraphs.append(values)

answer = -float('inf')
for i in range(n):
    index = ps[i] - 1
    value = cs[index]

    searchI = 0
    while True:
        vg = vGraphs[searchI]
        if value in vg:
            currentGraph = vg
            break
        searchI += 1

    total = sum(currentGraph)

    currentSum = 0
    count = 0
    ci = i
    while True:
        count += 1
        if count > k:
            break
        loop = (k - count) // len(currentGraph)
        multi = max(0, total) * loop

        ci = ps[ci] - 1

        currentV = cs[ci]
        currentSum += currentV

        answer = max(answer, multi + currentSum)
        if ci == i:
            break

print(answer)

### FIXED CODE ###

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


ps = list(map(int, input().split()))
cs = list(map(int, input().split()))

graphs = []
vGraphs = []
flags = [False]*n
sumDict = dict()
for i in range(len(ps)):
    p = ps[i]
    index = p - 1
    if flags[index]:
        continue

    current = set()
    values = set()
    currentIndex = index
    while True:
        if flags[currentIndex]:
            break

        current.add(currentIndex)
        values.add(cs[currentIndex])
        flags[currentIndex] = True
        nextIndex = ps[currentIndex] - 1
        currentIndex = nextIndex
    graphs.append(current)
    vGraphs.append(values)

answer = -float('inf')
for i in range(n):

    searchI = 0
    loopSum = 0
    nextIndex = i
    loopCount = 0
    while True:
        nextIndex = ps[nextIndex] - 1
        loopSum += cs[nextIndex]
        loopCount += 1
        if nextIndex == i:
            break

    total = loopSum

    currentSum = 0
    count = 0
    ci = i
    while True:
        count += 1
        if count > k:
            break
        loop = (k - count) // loopCount
        multi = max(0, total) * loop

        ci = ps[ci] - 1

        currentV = cs[ci]
        currentSum += currentV

        answer = max(answer, multi + currentSum)
        if ci == i:
            break

print(answer)
### BUGGY CODE ###

a,b,c,x,y=map(int,input().split())
l=[]
for i in range(10**8):
    s=c*i*2+a*max(0,x-i)+b*max(0,y-i)
    l.append(s)
print(min(l))


### FIXED CODE ###

a,b,c,x,y=map(int,input().split())
l=[]
for i in range(10**6):
    s=c*i*2+a*max(0,x-i)+b*max(0,y-i)
    l.append(s)
print(min(l))
### BUGGY CODE ###

import math
N = int(input())

def make_prime_list_2(num):
    if num < 2:
        return []

    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

P = make_prime_list_2(math.floor(math.sqrt(N)))
def div(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        divisor_num = 1
        for prime in P:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

ans = 0
for c in range(1, N):
    ans += div(N-c)

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1, N):
    ans += (N-1)//a
print(ans)
### BUGGY CODE ###

N = int(input())
a=1
for i in range(1,N+1):
    a*=i
print(a%(10**9+7))

### FIXED CODE ###

N = int(input())
a=1
for i in range(1,N+1):
    a*=i
    a%=(10**9+7)
print(a%(10**9+7))
### BUGGY CODE ###

N = int(input())
A = [input() for _ in range(N)]
tmp = 0
for j in range(N):
    tmp = A.pop(j)
    print(max(A))
    A.insert(j,tmp)


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
if N == 2:
    for j in A[::-1]:
        print(j)
else:
    tmp = sorted(A)
    del tmp[0:(N-2)]
    for i in range(N):
        if A[i] == tmp[1]:
            print(tmp[0])
        else:
            print(tmp[1])
### BUGGY CODE ###

N,M,R=map(int,input().split())
X=list(map(int,input().split()))
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for m in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c)}
    branch[b]|={(a,c)}
def makedist(x):
    dist=[float('inf')]*(N+1)
    dist[x]=0
    check=[x]
    while len(check)>0:
        now=check.pop()
        for b in branch[now]:
            if dist[now]+b[1]<dist[b[0]]:
                dist[b[0]]=dist[now]+b[1]
                check.append(b[0])
    return dist
data=dict()
for x in X:
    data[x]=makedist(x)
notvisit=set(X)
def roop(now,D,notvisit,ans):
    if len(notvisit)==0:
        return min(D,ans)
    for nex in notvisit:
        ans=roop(nex,D+data[now][nex],notvisit-{nex,},ans)
    return ans
ans=float('inf')
for x in X:
    ans=min(ans,roop(x,0,set(X),float('inf')))
print(ans)

### FIXED CODE ###

N,M,R=map(int,input().split())
X=list(map(int,input().split()))
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for m in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c)}
    branch[b]|={(a,c)}
def makedist(x):
    dist=[float('inf')]*(N+1)
    dist[x]=0
    check={x,}
    while len(check)>0:
        now=check.pop()
        for b in branch[now]:
            if dist[now]+b[1]<dist[b[0]]:
                dist[b[0]]=dist[now]+b[1]
                check|={b[0],}
    return dist
data=dict()
for x in X:
    data[x]=makedist(x)
def roop(now,D,notvisit,ans):
    if len(notvisit)==0:
        return min(D,ans)
    for nex in notvisit:
        ans=roop(nex,D+data[now][nex],notvisit-{nex,},ans)
    return ans
ans=float('inf')
for x in X:
    ans=min(ans,roop(x,0,set(X),float('inf')))
print(ans)