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

import sys
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

#print(edges)

task = [[] for _ in range(N+1)]
for i in range(Q):
    p, x = map(int, input().split())
    task[p].append(x)

#rint(task)

task_sum = [[] for _ in range(N+1)]
for i in range(N+1):
    task_sum[i].append(sum(task[i]))

#print('task_sum:', task_sum)

cnt = [[] for i in range(N+1)]

#print(cnt)

#最初はdfs(1, -1, task_sum[1])

def dfs(v, p, cost):
        
    for nv in edges[v]:
        if nv == p:
            continue
        
        dfs(nv, v, cost+task_sum[nv])

    cnt[v].append(cost)

dfs(1, -1, task_sum[1])

#print(cnt)
for i in range(1, N+1):
    print(int(sum(cnt[i][0])), end=' ')

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
g = [[] for _ in range(N+1)]
for a,b in AB:
    g[a].append(b)
    g[b].append(a)
 
cnt = [0] * (N+1)
for p,x in PX:
    cnt[p] += x

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

print(' '.join(map(str, cnt[1:])))
### BUGGY CODE ###

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

res = []
for _ in range(M):
  B, C = map(int,input().split())
  res += [C]*B

X = A+res
X.sort(reverse = True)
print(sum(X[:N]))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key = lambda x: -x[1])

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

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

DP = [[-10**9 for i in range((N+1)//2)] for i in range(N)]

DP[0][0] = A[0]
for i in range(1,N):
    DP[i][0] = max(DP[i-1][0],A[i])

for i in range(1,N//2-1):
    DP[2*i][i] = DP[2*(i-1)][i-1] + A[2*i]

for i in range(3,N):
    for j in range(N//2-(N-i+1)//2-1,(i+1)//2):
        DP[i][j] = max(DP[i-1][j],DP[i-2][j-1]+A[i])

print(DP[N-1][N//2-1])


### FIXED CODE ###

from collections import defaultdict

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

DP = defaultdict(lambda: -10**18)

DP[(0,0)] = A[0]

for i in range(1,N):
    for j in range((i+1)//2-1,(i+2)//2):
        if j == 0:
            DP[(i,0)] = max(DP[(i-1,0)],A[i])
        else:
            DP[(i,j)] = max(DP[(i-1,j)],DP[(i-2,j-1)]+A[i])

print(DP[(N-1,N//2-1)])
### BUGGY CODE ###

import numpy as np

def main():
  n=int(input())
  s=input()
  dp=np.array([[0]*(n+1) for i in range(n+1)])
  for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
  #for i in dp:
  #  print(i)
  
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)      
        

if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
  #for i in dp:
  #  print(i)
  
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)      
        

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

N=int(input())
X=[]
x=[]
for i in range(N):
    a,b=map(int,list(input().split(" ")))
    X.append(a+b)
    x.append(a-b)

def nibun(lis,x):
    i=len(lis)
    if i==1:
        if lis[0]<=x:
            return lis[0]
    elif lis[i//2]==x:
        return x
    else:
        if x<lis[i//2]:
            return nibun(lis[:i//2],x)
        else:
            return nibun(lis[i//2:],x)
    
X.sort()
x.sort()
a={}
a[x[0]]=0
a[X[0]]=1
for i in range(1,N):
    if nibun(X,x[i])==None:
        a[x[i]]=0
    else:
        a[x[i]]=a[nibun(X,x[i])]
    a[X[i]]=max(a[X[i-1]],a[x[i]]+1)
print(a[X[N-1]])

### FIXED CODE ###

N=int(input())
X=[]
for i in range(N):
    a,b=map(int,list(input().split(" ")))
    X.append([a+b,a-b])
X.sort()
D={}
D[0]=1
exe=[0]
for i in range(1,N):
    k=X[i][0]
    if X[i][1]<X[exe[-1]][0]:
        D[i]=D[exe[-1]]
    else:
        D[i]=D[exe[-1]]+1
        exe.append(i)
print(len(exe))
### BUGGY CODE ###

n,k,*a=map(int,open(0).read().split())

from fractions import gcd


G=a[0]
for i in a:
    G=gcd(G,i)
    
A=max(a)
if k>A:
    print("IMPOSSIBLE")
    exit()
    
while A>0:
    if k==A:
        print("POSSIBLE")
        exit()
    A-=G
print("IMPOSSIBLE")

### FIXED CODE ###

n,k,*a=map(int,open(0).read().split())

from fractions import gcd


G=a[0]
for i in a:
    G=gcd(G,i)
    
A=max(a)
if k>A:
    print("IMPOSSIBLE")
    exit()
    
while A>0:
    if k==A:
        print("POSSIBLE")
        exit()
    A-=G
print("IMPOSSIBLE")
### BUGGY CODE ###

N, K = map(int, input().split())
for p in range(K):
  if (N - p) % K == 0 or (N + p) % K == 0:
    print(p)
    break
  elif (N - (K - p)) % K == 0 or (N + (K - p)) % K == 0:
    print(K - p)
    break

### FIXED CODE ###

N, K = map(int, input().split())
print(min(N%K, K-N%K))
### BUGGY CODE ###

from bisect import bisect_right

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

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[float('inf')]*(n+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(min(i+2, 50)):
        dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 +
                         shop[i][0]*(dp[i][j-1]+1) + shop[i][1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(n+1):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)


### FIXED CODE ###

from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


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

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[INF for _ in range(31)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for i in range(n):
    for j in range(m):
        if (shop[i][0]+1)*(dp[i][j]+1) + shop[i][1] > t:
            dp[i+1][j+1] = dp[i][j+1]
        else:
            dp[i+1][j+1] = min(dp[i][j+1], (shop[i][0]+1)
                               * (dp[i][j]+1) + shop[i][1])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

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

def main():
    N = int(input())
    D = [int(_) for _ in input().split()]
    M = int(input())
    T = [int(_) for _ in input().split()]

    if N < M:
        print("NO")
        return

    for i in range(M):
        target = T[i]
        if D.count(target) >= 1:
            D.remove(target)
        else:
            print("NO")
            return
    
    print("YES")


if __name__ == "__main__":
    main()

### FIXED CODE ###

import collections

def main():
    N = int(input())
    D = [int(_) for _ in input().split()]
    M = int(input())
    T = [int(_) for _ in input().split()]
    Dd = collections.Counter(D)
 
    if N < M:
        print("NO")
        return

    for i in range(M):
        target = T[i]
        if Dd[target] >= 1:
            Dd[target] = Dd[target] - 1
        else:
            print("NO")
            return
    
    print("YES")


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

# 初期入力
N = int(input())
import numpy as np
koufuku = np.array( [list(map(int, input().split())) for i in range(N)] ,dtype=int)
dp_ko_np = np.zeros((N,2),dtype=int) 
dp_ko_np[0,0] = max( koufuku[0,:] )
dp_ko_np[0,1] = np.argmax(koufuku[0,:]) 

#
for i in range(N-1):
    # 翌日最大値のindex not 当日の保存していたindex(前日があるので、当日の最大値とは限らない)
    tomorr_i = np.argmax(koufuku[i+1,:]) # 翌日の最大値のindex
    if tomorr_i != dp_ko_np[i,1]: 
        dp_ko_np[i+1,0] = dp_ko_np[i][0] + np.max(koufuku[i+1,:] ) # 累積＋翌日の最大値
        dp_ko_np[i+1,1] = np.argmax(koufuku[i+1,:]) # 翌日のindex
    else:
        dp_ko_np[i+1,0] = dp_ko_np[i][0] + np.sort( koufuku[i+1,:] )[-2] # 累積＋2番目に大きい値
        dp_ko_np[i+1,1] = koufuku[i+1,:].argsort()[-2] # 2番目に大きい値のindex

print(dp_ko_np[N-1,0])

### FIXED CODE ###

"""
参考 Xenous
if sortを少なくし、maxで処理
""" 
# 初期入力
N = int(input())
a=[]
b=[]
c=[]
for i in range(N):
    a1,b1,c1 = (int(x) for x in input().split())
    
    a.append(a1)
    b.append(b1)
    c.append(c1)

dp_A = [0]*(N) ;dp_A[0] =a[0] 
dp_B = [0]*(N) ;dp_B[0] =b[0] 
dp_C = [0]*(N) ;dp_C[0] =c[0] 


#
for i in range(0,N-1):
    dp_A[i+1] = max(dp_B[i] + a[i+1] , dp_C[i] + a[i+1])
    dp_B[i+1] = max(dp_A[i] + b[i+1] , dp_C[i] + b[i+1])
    dp_C[i+1] = max(dp_A[i] + c[i+1] , dp_B[i] + c[i+1])
print(max (dp_A[N-1],dp_B[N-1],dp_C[N-1]) )
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
MOD = 1000000007
for i in range(n-1):
    for j in range(i+1, n):
      ans = ans + a[i]*a[j]
      ans = ans % MOD
print(ans)

### FIXED CODE ###

# p = list(map(int, input().split()))
# a, b, c = map(int, input().split())
# n = int(input())
# s = input()
# print(i, end=" ")


n = int(input())
a = list(map(int, input().split()))
ans = 0
mod = 1000000007
sum = 0
for i in range(n):
    sum = sum + a[i]
    sum = sum % mod
    
for i in range(n):
    sum = sum - a[i]
    if sum < 0:
        sum = sum + mod
    ans = ans + a[i] * sum
    ans = ans % mod
print(ans)
### BUGGY CODE ###

from collections import deque
import time
start = time.time()#計測始
 
s = str(input())
n=len(s)
#span :int=1
mlist=deque("0")
slist :str=""
  
for span in range(n):
  slist = str(s[n-span-1]) + slist
  #print(str(slist))
  m = int(slist)%2019
  mlist.append(str(m))
  #span+=1
  
ll=len(mlist)
l=len(set(mlist))
print(ll-l)
end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力

### FIXED CODE ###

import time

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

#start = time.time()#計測始
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
#end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力
### BUGGY CODE ###

N = int(input())

for i in range(1, 3501):
    for j in range(1, 3501):
        if (4 * i * j - N * j - N * i) != 0:
            w = (N * i * j) // (4 * i * j - N * j - N * i)
            if w > 0 and 4 / N == 1/ i + 1/j + 1 /w:
                print(i, j, w)
                exit()


### FIXED CODE ###

N = int(input())

for i in range(1, 3501):
    for j in range(1, 3501):
        if (4 * i * j - N * i - N * j) <= 0:
            continue
        if (N * i * j) % (4 * i * j - N * j - N * i) == 0:
            print(i, j, (N * i * j) // (4 * i * j - N * j - N * i))
            exit()
### BUGGY CODE ###

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

mod = 10**9 + 7
ans = 0
k=1
while A[-1]>0:
    t = 0
    for i in range(N):
        t+=A[i]%2
        A[i]//=2
    ans = (ans + (N-t)*t*(2**(k-1))%mod)%mod
    k +=1
print(ans)


### FIXED CODE ###

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

mod = 10**9 + 7
def mulmod(s):
    r = 1
    for i in s:
        r = r*i%mod
    return r


ans = 0
k=1
while A[-1]>0:
    t = 0
    for i in range(N):
        t+=A[i]%2
        A[i]//=2
    r = [N-t, t, pow(2, k-1, mod)]
    ans = (ans + mulmod(r))%mod
    k +=1
print(ans)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

uf = UnionFind(n)

con = [0] * (m+1)#convenience
x = [0] * (m+1)
y = [0] * (m+1)

con[m] = 0

for i in range(1,m+1):
    x[i], y[i] = map(int, input().split())
    
for j in range(m-1,0,-1):
    uf.union(x[j+1],y[j+1])
    
    for k in range(1,n+1):
        for l in range(1,n+1):
            if uf.same_check(k,l):
                con[j] = con[j] + 1
    
    con[j] = int((con[j] - n) / 2)

N = int(n * (n-1) / 2)

for i in range(1,m+1):
    print(N-con[i])
        

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
        self.con = [0] * (m+1)#convenience

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y, j):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.con[j] = self.con[j+1] + self.size[x] * self.size[y]
        else:
            self.con[j] = self.con[j+1]
        #print([x,y])
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] = self.size[x] + self.size[y]
            self.size[x] = 0
        else:
            self.par[y] = x
            if x != y:
                self.size[x] = self.size[x] + self.size[y]
                self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

uf = UnionFind(n)

x = [0] * (m+1)
y = [0] * (m+1)


for i in range(1,m+1):
    x[i], y[i] = map(int, input().split())
    #print([x,y])
    
for j in range(m-1,0,-1):
    #print([x[j+1],y[j+1]])
    uf.union(x[j+1],y[j+1],j)
    
    #print(uf.size)
    #print(uf.con)

N = int(n * (n-1) / 2)

for i in range(1,m+1):
    print(N-uf.con[i])
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            check[y][x] = 0
            q.append((y, x, 0))

dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]

while q:
    y, x, cnt = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < H and 0 <= nx < W:
            if check[ny][nx] == -1 or cnt+1 < check[ny][nx]:
                check[ny][nx] = cnt + 1
                q.append((ny, nx, cnt+1))


print(max([max(c) for c in check]))

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            check[y][x] = 0
            q.append((y, x, 0))

dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]

while q:
    y, x, cnt = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < H and 0 <= nx < W:
            if check[ny][nx] == -1 or cnt+1 < check[ny][nx]:
                check[ny][nx] = cnt + 1
                q.append((ny, nx, cnt+1))


print(max([max(c) for c in check]))
### BUGGY CODE ###

s = list(input())
if len(s) <= 2:
    print(0)
else:
    i = 2
    ans = 0
    while i < len(s):
        if s[i] == "C" and s[i-1] == "B" and s[i-2] == "A":
            s[i] = "A"
            s[i-1] = "C"
            s[i-2] = "B"
            ans += 1
            if i-3 >= 0 and s[i-3] == "A":
                i -= 1
            else:
                i += 2
        else:
            i += 1
    print(ans)

### FIXED CODE ###

s = input()
s = s.replace("BC", "X")

ans = 0
a_count = 0

for i in range(len(s)):
    if s[i] == "A":
        a_count += 1
    elif s[i] == "X":
        ans += a_count
    else:
        a_count = 0

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

nums = list(map(lambda x: int(x), input().split(" ")))
n = nums[0]
k = nums[1]
ps = list(map(lambda x: (int(x) + 1) / 2, input().split(" ")))
res = 0.0
for i in range(n - k + 1):
    res = max(res, sum(ps[i:i+k]))
print(res)

### FIXED CODE ###

nums = list(map(lambda x: int(x), input().split(" ")))
n = nums[0]
k = nums[1]
ps = list(map(lambda x: (int(x) + 1) / 2, input().split(" ")))
res = 0.0
su = 0.0
sums = [0] * n
for i, s in enumerate(ps):
    su = su + s
    sums[i] = su
for i in range(n - k + 1):
    if i == 0:
        res = sums[k - 1]
    else:
        res = max(res, sums[i + k - 1] - sums[i - 1] )
print(res)
### BUGGY CODE ###

INF = int(1e9)
N, M, K = list(map(int, input().split()))
R = list(map(lambda x: int(x) - 1, input().split()))

G = [[INF] * N for i in range(N)]
for i in range(N):
    G[i][i] = 0
            
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a = a - 1
    b = b - 1
    G[a][b] = G[b][a] = c
    
ls = range(N)
for k in ls:
    for i in ls:
        for j in ls:
            x = G[i][k] + G[k][j]
            if x < G[i][j]:
                G[i][j] = G[j][i] = x

dp = [[INF] * (1<<K) for i in range(K)]
for i in range(K):
    dp[i][1<<i] = 0

for bit in range(1<<K):
    for pre in range(K):
        if (bit >> pre) & 1 == 0:
            continue
        for to in range(K):
            if (bit >> to) & 1 == 1:
                continue
            cost = dp[pre][bit] + G[R[pre]][R[to]]
            nbit = bit | (1<<to)
            if dp[to][nbit] > cost:
                dp[to][nbit] = cost

ans = INF     
for pre in range(K):
    ans = min(ans, dp[pre][(1<<K) - 1])
print (ans)
              


### FIXED CODE ###

INF = int(1e9)
N, M, K = list(map(int, input().split()))
R = list(map(lambda x: int(x) - 1, input().split()))

G = [[INF] * N for i in range(N)]
for i in range(N):
    G[i][i] = 0
            
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a = a - 1
    b = b - 1
    G[a][b] = G[b][a] = c
    
ls = range(N)
for k in ls:
    for i in ls:
        for j in range(i+1,N):
            x = G[i][k] + G[k][j]
            if x < G[i][j]:
                G[i][j] = G[j][i] = x

dp = [[INF] * (1<<K) for i in range(K)]
for i in range(K):
    dp[i][1<<i] = 0

for bit in range(1<<K):
    for pre in range(K):
        if (bit >> pre) & 1 == 0:
            continue
        for to in range(K):
            if (bit >> to) & 1 == 1:
                continue
            cost = dp[pre][bit] + G[R[pre]][R[to]]
            nbit = bit | (1<<to)
            if dp[to][nbit] > cost:
                dp[to][nbit] = cost

ans = INF     
for pre in range(K):
    ans = min(ans, dp[pre][(1<<K) - 1])
print (ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split(" ")]

b = []
for i in range(n):
  b.append(str(a.index(i+1)+1))

print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = [0] * n
c = 1
for i in input().split(" "):
  a[int(i) - 1] = str(c)
  c += 1

print(" ".join(a))
### BUGGY CODE ###

X,Y = map(int,input().split())
X_ = X
while X_ <= 10**18:
  if X == Y:
    print(-1)
    exit()
  X_ += X
  if X%Y != 0:
    print(X)
    exit()

print(-1)

### FIXED CODE ###

X,Y = map(int,input().split())
X_ = X
while X_ <= 10**9:
  if X == Y:
    print(-1)
    exit()
  X_ += X
  if X%Y != 0:
    print(X)
    exit()

print(-1)
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
m = ["#"*(w+2)]+["#"+input()+"#" for i in range(h)]+["#"*(w+2)]
temp = [[-1]*(w+2) for i in range(h+2)]
opt = [(1,0),(0,1),(-1,0),(0,-1)]
dq = deque()
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if m[i][j] == "#":
            dq.append((i,j))
            temp[i][j] = 0
while dq:
    y,x = dq.popleft()
    for i in opt:
        y1 = y+i[0]
        x1 = x+i[1]
        if m[y1][x1] == "." and temp[y1][x1] == -1:
            temp[y1][x1] = temp[y][x]+1
            ans = max(ans,temp[y1][x1])
            dq.append((y1,x1))
print(ans)

### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
m = ["#"*(w+2)]+["#"+input()+"#" for i in range(h)]+["#"*(w+2)]
temp = [[-1]*(w+2) for i in range(h+2)]
opt = [(1,0),(0,1),(-1,0),(0,-1)]
dq = deque()
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if m[i][j] == "#":
            dq.append((i,j))
            temp[i][j] = 0
while dq:
    y,x = dq.popleft()
    for i in opt:
        y1 = y+i[0]
        x1 = x+i[1]
        if m[y1][x1] == "." and temp[y1][x1] == -1:
            temp[y1][x1] = temp[y][x]+1
            ans = max(ans,temp[y1][x1])
            dq.append((y1,x1))
print(ans)