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

INFTY = 10**12
N,M,L = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
F = {i:[] for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N+1):
        if dist[i][j]<=L:
            F[i].append(j)
dist2 = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in F[i]:
        dist2[i][j] = 1
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist2[i][j] = min(dist2[i][j],dist2[i][k]+dist2[k][j])
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    if dist2[s][t]>=INFTY:
        print(-1)
    else:
        print(dist2[s][t]-1)

### FIXED CODE ###

INFTY = 10**12
def wf(H):
    d = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        d[i][i] = 0
        if i in H:
            for x in H[i]:
                j,c = x[0],x[1]
                d[i][j] = c
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
G = {}
for _ in range(M):
    A,B,C = map(int,input().split())
    if A not in G:
        G[A] = []
    G[A].append((B,C))
    if B not in G:
        G[B] = []
    G[B].append((A,C))
d1 = wf(G)
F = {}
for i in range(1,N):
    for j in range(i+1,N+1):
        if d1[i][j]<=L:
            if i not in F:
                F[i] = []
            F[i].append((j,1))
            if j not in F:
                F[j] = []
            F[j].append((i,1))
d2 = wf(F)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    if d2[s][t]<INFTY:
        print(d2[s][t]-1)
    else:
        print(-1)
### BUGGY CODE ###

h,n,*L=map(int,open(0).read().split())
dp=[float('inf')]*(h+10100)
dp[0]=0
for a,b in zip(*[iter(L)]*2):
    for i in range(h):
        t=dp[i]+b
        if t<dp[i+a]:
            dp[i+a]=dp[i]+b
print(min(dp[h:]))

### FIXED CODE ###

h,n,*L=map(int,open(0).read().split())
dp=[float('inf')]*(h+10100)
dp[0]=0
for a,b in zip(*[iter(L)]*2):
    for i in range(h):
        t=dp[i]+b
        if t<dp[i+a]:
            dp[i+a]=dp[i]+b
print(min(dp[h:]))
### BUGGY CODE ###

from math import gcd
 
k=int(input())
 
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1, k+1):
      t_gcd=gcd(i,j)
      ans+=gcd(t_gcd,l)
 
print(ans)

### FIXED CODE ###

from math import gcd
 
k=int(input())
 
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1, k+1):
      ans+=gcd(gcd(i,j),l)
 
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

A = [[]] + A

cnt = 0
ok = True
q = list(range(1, N+1))

for _ in range(N * (N - 1) // 2):
    can_match_today = [False] * (N+1)
    fin = True
    match = False
    nq = []
    for i in q:
        if can_match_today[i] or not A[i]:
            continue

        fin = False
        l = A[i][-1]

        if can_match_today[l]:
            continue
        r = A[l][-1]

        if r == i:
            match = True
            can_match_today[l] = True
            can_match_today[i] = True
            A[l].pop()
            A[i].pop()
            nq.append(l)
            nq.append(i)

    if fin:
        break

    if not match:
        ok = False
        break

    cnt += 1
    q = nq


if ok:
    print(cnt)
else:
    print(-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

A = [[-1]] + A


def check(a, q=[]):
    if not A[a]:
        return False

    b = A[a][-1]
    b_op = A[b][-1]

    ok = False
    if a == b_op:
        ok = True

        if b < a:
            a, b = b, a
        q.append((a, b))

    return ok


q = []
for i in range(1, N + 1):
    check(i, q)

q = list(set(q))

day = 0
while q:
    nq = []
    for a, b in q:
        A[a].pop()
        A[b].pop()
        check(a, nq)
        check(b, nq)

    day += 1
    q = list(set(nq))

for i in range(1, N + 1):
    if len(A[i]) != 0:
        print(-1)
        exit()

print(day)
exit()
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
np,nm=[],[]
for i in range(N):
    np.append(A[i]+i)
    nm.append(i-A[i])
sp,sm=sorted(np),sorted(nm)
ans=0
for i in range(N):
    p,m=np[i],nm[i]
    l,r=0,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<=p:
            l=x
        else:
            r=x
    while sm[l]==p and l>=0:
        ans+=1
        l-=1
    l,r=0,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<=m:
            l=x
        else:
            r=x
    while sp[l]==m and l>=0:
        ans+=1
        l-=1
print(ans//2)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
np,nm=[],[]
for i in range(N):
    np.append(A[i]+i)
    nm.append(i-A[i])
sp,sm=sorted(np),sorted(nm)
ans=0
for i in range(N):
    p,m=np[i],nm[i]
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<=p:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<p:
            l=x
        else:
            r=x
    ans+=tmp-l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<=m:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<m:
            l=x
        else:
            r=x
    ans+=tmp-l
print(ans//2)
### BUGGY CODE ###

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

for i in range(N):
  a = A[i]
  del A[i]
  print(max(A))
  A.insert(i, a)

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
M = max(A)
c = A.count(M)
a = list(set(A))
a.sort(reverse=True)
 
for i in range(N):
  if A[i] != M:
    print(M)
  else:
    if c >= 2:
      print(M)
    else:
      print(a[1])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    a[-1] //= 2
    for j in range(1, n):
        if a[-j] > a[-j - 1]:
            break
        a[-j], a[-j - 1] = a[-j - 1], a[-j]
print(sum(a))

### FIXED CODE ###

class heap():
    def __init__(self, maxcom=True):
        if maxcom:
            self.compare = lambda x, y: x > y
        else:
            self.compare = lambda x, y: x < y

    def heappush(self, x, heap):
        heap.append(x)
        length = len(heap)
        pointer = length
        while True:
            if pointer == 1:
                break
            if self.compare(heap[pointer - 1], heap[(pointer >> 1) - 1]):
                heap[pointer - 1], heap[(pointer >> 1) - 1] = heap[(pointer >> 1) - 1], heap[pointer - 1]
                pointer = pointer >> 1
            else:
                break

    def heapreplace(self, function, heap):
        heap[0] = function(heap[0])
        pointer = 1
        length = len(heap)
        while True:
            if (pointer << 1) > length:
                break
            elif (pointer << 1) + 1 > length :
                if self.compare(heap[(pointer << 1) - 1], heap[pointer - 1]):
                    heap[(pointer << 1) - 1], heap[pointer - 1] = heap[pointer - 1], heap[(pointer << 1) - 1]
                else:
                    break
            else:
                if self.compare(heap[(pointer << 1) - 1], heap[pointer << 1]):
                    next_pointer = pointer << 1
                else:
                    next_pointer = (pointer << 1) + 1
                if self.compare(heap[next_pointer - 1], heap[pointer - 1]):
                    heap[next_pointer - 1], heap[pointer - 1] = heap[pointer - 1], heap[next_pointer - 1]
                    pointer=next_pointer
                else:
                    break


n, m = map(int, input().split())
a = map(int, input().split())
heapq = []
heapc=heap(True)
for i in a:
    heapc.heappush(i,heapq)
for _ in range(m):
    heapc.heapreplace(lambda x:x>>1,heapq)
print(sum(heapq))
### BUGGY CODE ###

N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

S = {}
DP = [0] * N
for i in range(N - 2, -1, -1):
  cnt = 0
  su = 0
  a = 0
  amax = 0
  for x in R[i]:
    t = DP[x] + 1
    if t >= amax:
      amax = DP[x] + 1
      a = x
    su += DP[x] + 1
    cnt += 1
  DP[i] = su / cnt
  S[i] = a

ans = DP[0]
for i in range(N - 1):
  DP = [0] * N
  for j in range(N - 2, -1, -1):
    A = []
    su = 0
    for x in R[j]:
      if i == j:
        if S[i] == x:
          continue
      A.append(DP[x] + 1)
      su += A[-1]
    if len(A) == 0:
      break
    DP[j] = su / len(A)
  else:
    ans = min(DP[0], ans)

print(ans)



### FIXED CODE ###

N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [0] * N
ans = N
D = [0] * N
for i in range(N - 2, -1, -1):
  ma = 0
  su = 0
  le = len(R[i])
  for j in R[i]:
    su += DP[j]
    ma = max(ma, DP[j])

  DP[i] = su / le + 1 
  if le == 1:
    D[i] = 0
  else:
    D[i] = DP[i] - (((su - ma) / (le - 1)) + 1)

P = [0] * N 
P[0] = 1
ma = 0
man = -1
for i in range(N - 1):
  t = P[i] / len(R[i])
  for j in R[i]:
    P[j] += t 
  t = P[i] * D[i]
  R[i].sort()
  if ma < t:
    ma = t
    man = i
 
if ma == -1:
  print(DP[0])
else:
  print(DP[0] - ma)
### BUGGY CODE ###

N,M=map(int, input().split())
H=list(map(int,input().split()))
List=[list(map(int,input().split())) for i in range(M)]
ans=0
alllist=[[0 for i in range(N)]for j in range(N)]

for j in range(M):
    alllist[List[j][0]-1][List[j][1]-1]=1
    alllist[List[j][1]-1][List[j][0]-1]=1


for s in range(N):
    flag=True
    for t in range(N):
        if H[s]>alllist[s][t]*H[t]:
            a=1
        else:
            flag=False   
            break
    if flag:
        ans=ans+1
print(ans)  

### FIXED CODE ###

N,M=map(int, input().split())
H=list(map(int,input().split()))
List=[list(map(int,input().split())) for i in range(M)]

sup_list=[1 for i in range(N)]

for j in range(M):
    if H[List[j][0]-1]>H[List[j][1]-1]:
        sup_list[List[j][1]-1]=0
    elif H[List[j][0]-1]==H[List[j][1]-1]:
        sup_list[List[j][0]-1]=0
        sup_list[List[j][1]-1]=0
    else:
        sup_list[List[j][0]-1]=0


print(sum(sup_list))
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
cnt = 0
res = []
for i in range(n - 1, -1, -1):
    c = i + 1
    if (A[i] % 2 == 1):
        cnt += 1
        res.append(c)
        for k in range(1, int(c ** 0.5) + 1):
            if (c % k == 0):
                if (k != c // k):
                    A[k - 1] -= 1
                    A[c // k - 1] -= 1
                else:
                    A[k - 1] -= 1
print(cnt)
print(*res)

### FIXED CODE ###

from copy import deepcopy
n = int(input())
A = list(map(int,input().split()))
AA = deepcopy(A)
f = [0]*n
m = 0
b = []
for i in range(n-1,0,-1):
    if A[i]%2==0:
        continue
    b.append(i+1)
    m += 1
    for k in range(1,int((i+1)**0.5)+1):
        if (i+1)%k == 0:
            if(k-1!=(i+1)//k-1):
                A[k-1] -= 1
                A[(i+1)//k-1] -= 1
                f[k-1] += 1
                f[(i+1)//k-1] += 1
            else:
                A[k-1] -= 1
                f[k-1] += 1

if f[0]%2 !=AA[0]%2:
    b.append(1)
    m += 1
for i in range(1,n):
    if f[i]%2 != AA[i]:
        print(-1)
        exit()
print(m)
if m==0:
    exit()
print(*b)
### BUGGY CODE ###

n=int(input())
for i in range(1,n+1):
    e=0
    for j in range(1,101):
        if(j*j>=n):
            break
        for k in range(1,101):
            if(k*k>=n):
                break
            for l in range(1,101):
                if(l*l>=n):
                    break
                if((j*j)+(k*k)+(l*l)+(j*k)+(k*l)+(l*j)==i):
                    e=e+1
    print(e)

### FIXED CODE ###

from math import sqrt, floor

N = int(input())
d = [0] * (N+1)

k = floor(sqrt(N))
for x in range(1, k):
    for y in range(1, k):
        for z in range(1, k):
            c = x*x + y*y + z*z + x*y + y*z + z*x
            if 1 <= c <= N:
                d[c] += 1


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

n, x = map(int, input().split(' '))

ans = n
c = [x, n-x]
while (c[0] != c[1]):
    ans += 2 * min(c)
    c = [min(c), max(c)-min(c)]
print(ans+c[0])


### FIXED CODE ###

def sub(a, b):
    if (a%b == 0):
        return a//b-1
    return a//b

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

n, x = map(int, input().split(' '))
ans = n
c = [x, n-x]
while (c[0] != c[1]):
    c = [min(c), max(c)]
    ans += 2*sub(c[1], c[0])*c[0]
    c[1] = mod(c[1], c[0])
print(ans+c[0])
### BUGGY CODE ###

import itertools

inf = 10 ** 9
n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
dis = [[inf for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

# 全ての頂点間の最短距離を算出、
for k in range(len(dis)):
    for i in range(len(dis)):
        for j in range(len(dis)):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]


_min = inf
for iterR in itertools.permutations(r):
    _dis = 0
    for j in range(1, len(iterR)):
        _dis += dis[iterR[j]][iterR[j-1]]
    _min = min(_min, _dis)
print(_min)

"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""


### FIXED CODE ###

import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
dis = [[float("inf") for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

def war(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
    return dis
dis = war(dis)
_min = float("inf")
it = itertools.permutations(r)
for iterR in it:
    _dis = 0
    start = iterR[0] - 1
    for end in iterR[1:]:
        _dis += dis[start][end - 1]
        start = end - 1
    _min = min(_min, _dis)
print(_min)
### BUGGY CODE ###

from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i += 1

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)

ans = 0

for i,a in enumerate(B):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            continue
        elif d in keys:
            ok = False
            break
    if ok:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i += 1

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    elif not checks[a]:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

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

N = int(input())
S = [n for n in input()]
temp = []
result = []
for i in range(N-1):
  if S[i] == S[i+1]:
    temp.append(i)
for i in range(N):
  if i not in temp:
    result.append(S[i])
print(len(result))


### FIXED CODE ###

n=int(input());s=input();print(1+sum([s[i-1]!=s[i] for i in range(1,n)]))
### BUGGY CODE ###

def main():
    L, R = map(int, input().split())
    d = dict()
    for i in range(L, R+1):
        v = i % 2019
        if v not in d: d[v] = 1
        else: d[v] += 1

    min_r = 2018
    for i in range(2019):
        if i in d and d[i] > 1:
            min_r = min(min_r, (i*i) % 2019)
    for i in range(2018):
        for j in range(i+1, 2019):
            if i in d and j in d:
                min_r = min(min_r, (i*j) % 2019)

    return min_r



if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():
    L, R = map(int, input().split())
    d = dict()
    for i in range(L, min(R+1, L+2019*2)):
        v = i % 2019
        if v not in d: d[v] = 1
        else: d[v] += 1

    min_r = 2018
    for i in d:
        if i in d and d[i] > 1:
            min_r = min(min_r, (i*i) % 2019)

    for i in d:
        for j in d:
            if i < j: min_r = min(min_r, (i*j) % 2019)

    return min_r



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

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

for i in range(m):
    a.append(a[-1]/2)
    del a[-2]
    a.sort()

ans = 0
for i in range(n):
    ans += int(a[i])
print(ans)

### FIXED CODE ###

from heapq import heapify, heappop, heappush
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [-i for i in a]
heapify(a)

for i in range(m):
    x = heappop(a)
    heappush(a, int(x/2))

ans = 0
for i in range(n):
    ans += -a[i]
print(ans)
### BUGGY CODE ###

#import time
#time1=time.time()
N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x),abs(y-a)+1+abs(b-x))
    return ans
distance=[0]*(N-1)
for x in range(1,N):
    for y in range(2,N+1):
        if y<=x:
            continue
        a=shortest(x,y,X,Y)
        distance[a-1]+=1
for i in distance:
    print(i)
#time2=time.time()
#print(time2-time1)

### FIXED CODE ###

N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x),abs(y-a)+1+abs(b-x))
    return ans
distance=[0]*N
for x in range(1,N+1):
    for y in range(1,N+1):
        if y<=x:
            continue
        else:
            a=shortest(x,y,X,Y)
            distance[a-1]+=1
for i in range(N-1):
    print(distance[i])
### BUGGY CODE ###

N,W = map(int,input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]

for i in range(N):
    w[i],v[i] = map(int,input().split())

dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j+w[i] <= W:
            dp[i+1][j+w[i]] = max(dp[i][j], dp[i][j]+v[i])
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        else:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])

### FIXED CODE ###

N,W = map(int,input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]

for i in range(N):
    w[i],v[i] = map(int,input().split())

dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j+w[i] <= W:
            dp[i+1][j+w[i]] = max(dp[i][j], dp[i][j]+v[i])
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        else:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])
### BUGGY CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = []
B = []
C = []
D = [[] for _ in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(N):
        if i == j:
            D[i].append(0)
        else:
            D[i].append(inf)


for _ in range(M):
    a, b, c = map(int, input().split())
    D[a - 1][b - 1] = c
    D[b - 1][a - 1] = c


def WarshallFloyd(D):
    """
    >>> WarshallFloyd([[0, 1, 4], [1, 0, 1], [4, 1, 0]])
    [[0, 1, 2], [1, 0, 1], [2, 1, 0]]
    """
    for k in range(len(D)):
        for i in range(len(D)):
            for j in range(len(D)):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D


D = WarshallFloyd(D)
Min = inf
for e in permutations(r):
    s = 0
    for i in range(R - 1):
        s += D[e[i] - 1][e[i + 1] - 1]
    Min = min(s, Min)

print(Min)


### FIXED CODE ###

from itertools import permutations
import heapq
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
D = [[] for _ in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(N):
        if i == j:
            D[i].append(0)
        else:
            D[i].append(inf)

for _ in range(M):
    a, b, c = map(int, input().split())
    D[a - 1][b - 1] = c
    D[b - 1][a - 1] = c


def WarshallFloyd(D):
    """
    >>> WarshallFloyd([[0, 1, 4], [1, 0, 1], [4, 1, 0]])
    [[0, 1, 2], [1, 0, 1], [2, 1, 0]]
    """
    for k in range(len(D)):
        for i in range(len(D)):
            for j in range(len(D)):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D


def _dijkstra(D, s, F):
    q = []
    heapq.heappush(q, (0, s))
    while len(q) != 0:
        cost, index = heapq.heappop(q)
        if F[s][index] < cost:
            continue
        for i in range(len(D)):
            if cost + D[index][i] < F[s][i]:
                F[s][i] = cost + D[index][i]
                heapq.heappush(q, (F[s][i], i))
    return F


def Dijkstra(D):
    F = [[inf] * len(D) for _ in range(len(D))]
    for i in range(len(D)):
        F[i][i] = 0
        F = _dijkstra(D, i, F)
    return F


#W = WarshallFloyd(D)
D = Dijkstra(D)
# print(W)
# print(D)
Min = inf
for e in permutations(r):
    s = 0
    for i in range(R - 1):
        s += D[e[i] - 1][e[i + 1] - 1]
    Min = min(s, Min)

print(Min)