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

class BIT:
    """1-indexed BIT
    """

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        self.__size = size
        self.__bit = [0] * (self.__size+1)

    def add(self, idx: int, val: int):
        """位置 idx (1-indexed) に値 val をたす。
        :param idx: 値を追加したいインデックス
        :param val: 追加したい値
        """
        while idx <= self.__size:
            self.__bit[idx] += val
            idx += idx & (-idx)

    def sum(self, l: int, r: int)->int:
        """(l, r] の累積和を計算する。
        :param l: left index
        :param r: right index
        :return: (l, r] の累積和
        """
        return self.__sum__(r) - self.__sum__(l)

    def __sum__(self, idx: int)->int:
        s = 0
        while idx > 0:
            s += self.__bit[idx]
            idx -= idx & (-idx)
        return s


def inversion(A: list) -> int:
    bit = BIT(max(A))
    s = 0
    for a in A:
        s += bit.sum(0, a)
        bit.add(a, 1)

    return s


def check2(A: list, x: int)->int:
    n = len(A)
    S = [0] * (n + 1)
    for i in range(n):
        if x <= A[i]:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    m = min(S)
    return inversion([s - (m - 1) for s in S])


def median_of_medians(N: int, A: list) -> int:
    def check(x: int)->int:
        S = [0] * (N + 1)
        for i in range(N):
            if x <= A[i]:
                S[i + 1] = S[i] + 1
            else:
                S[i + 1] = S[i] - 1

        m = min(S)
        S = [s - (m - 1) for s in S]

        bit = BIT(max(S))
        s = 0
        for a in S:
            s += bit.sum(0, a)
            bit.add(a, 1)

        return s

    alpha = sorted(A)
    l, r = 0, N
    while r - l > 1:
        m = (r + l + 1) // 2
        if 2*check(alpha[m]) >= (N * (N + 1)) // 2:
            l = m
        else:
            r = m

    return alpha[l]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)


### FIXED CODE ###


def median_of_medians(N: int, A: list)->int:
    def search(c):
        bar = N
        r = 0
        res_nega = 0
        dp_arr = [0]*(2*N+1)
        for i in range(N):
            dp_arr[bar] += 1
            if A[i] < c:
                r += dp_arr[bar]
                bar += 1
            else:
                r -= (dp_arr[bar-1])
                bar -= 1
            res_nega += r
        return res_nega

    # binary search
    a_sorted = sorted(A)
    left = 0
    right = N
    mid = N // 2
    C = N*(N+1) // 2
    while True:
        if search(a_sorted[mid]) <= C // 2:
            if mid == N-1:
                break
            elif search(a_sorted[mid+1]) > C // 2:
                break
            else:
                left = mid
                mid = (mid + right) // 2
        else:
            right = mid + 1
            mid = (mid + left) // 2

    return a_sorted[mid]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

N = int(input())
# S = input()
# N, M = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
S = [sorted(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
for i, s in enumerate(S) :
    for ss in range(i + 1, N) :
        if s == S[ss] :
            ans += 1

print(ans)


### FIXED CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

N = int(input())
# S = input()
# N, M = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
S = [''.join(sorted(input())) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
dic = {}
for s in S :
    if not s in dic :
        dic[s] = 0
    
    ans += dic[s]
    dic[s] += 1

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

n = int(input())
an = [int(num) for num in input().split()]

answer = []
for index in range(1,len(an)+1):
  answer.append(str(an.index(index)+1))

print(" ".join(answer))

### FIXED CODE ###

n = int(input())
an = [int(num) for num in input().split()]

answer = [0 for _ in range(n)]
for index in range(n):
  answer[an[index] - 1] = str(index + 1)

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

N=list(map(int,input().split(" ")))
ans=[int(input()) for i in range(N[2])]	

point=[N[1] for i in range(N[0])]
def down(y):
	return y-1
for i in ans:
	point=list(map(down,point))
	point[i-1]+=1
#print(point)
for i in range(N[0]):
	if point[i]>0:
		print("Yes")
	else:
		print("No")

### FIXED CODE ###

N=list(map(int,input().split(" ")))
ans=[int(input()) for i in range(N[2])]	

point=[N[1]-N[2] for i in range(N[0])]

for i in ans:
	point[i-1]+=1
#print(point)
for i in range(N[0]):
	if point[i]>0:
		print("Yes")
	else:
		print("No")
### BUGGY CODE ###

from collections import deque

h , w = map(int,input().split())
ma = [["#"]*(w+2)]
cou = 0
for i in range(h):
    kar = ["#"]
    kar.extend(list(input()))
    cou += kar.count("#") - 1
    kar.append("#")
    ma.append(kar)
ma.append(["#"]*(w+2))

ans = [[-1 for i in range(w+2)] for j in range(h+2)]
ans[1][1] = 1
q = deque([(1,1)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if ma[nx][ny] == ".":
            q.append((nx,ny))
            ans[nx][ny] = ans[x][y] + 1
        if nx == h and ny == w:
            break

if ans[h][w] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h][w])

### FIXED CODE ###

from collections import deque
 
h , w = map(int,input().split())
cou = 0
ma = []
for i in range(h):
    kar = list(input())
    cou += kar.count("#")
    ma.append(kar)
 
 
ans = [[-1 for i in range(w)] for j in range(h)]
ans[0][0] = 1
q = deque([(0,0)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]
 
while q:
    x , y = q.popleft()
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if 0 <= nx <= h-1 and 0 <= ny <= w-1 and ans[nx][ny] == -1:
            if ma[nx][ny] == ".":
                q.append((nx,ny))
                ans[nx][ny] = ans[x][y] + 1
        if nx == h-1 and ny == w-1:
            break
 
if ans[h-1][w-1] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h-1][w-1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(N//R+1):
    for j in range(N//G+1):
        if i*R + j*G <= N and (N-i*R-j*G)%B == 0:
            ans += 1
print(int(ans))


### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(N//R+1):
    x = i * R
    for j in range((N-x)//G+1):
        
        y = j*G
        z = N - x-y
        if z>= 0 and z%B == 0:
            ans += 1
print(int(ans))
### BUGGY CODE ###

from functools import reduce
from itertools import product
N, M = map(int, input().split())
x, y, z = zip(*(map(int, input().split()) for _ in range(N)))


def f(a, b, c):
    return (
        sum(
            map(
                abs,
                reduce(
                    lambda acc, t: [
                        (0, 0, 0) if i == 0 else
                        (acc[i - 1][0] + t[0], acc[i - 1][1] + t[1], acc[i - 1][2] + t[2]) if sum(acc[i - 1]) + sum(t) > sum(acc[i]) else
                        acc[i]
                        for i in range(M + 1)
                    ],
                    zip(a, b, c),
                    [(0, 0, 0) for _ in range(M + 1)]
                )[M]
            )
        )
    )


def g(k, a):
    return [k * e for e in a]


ans = max(
    f(g(p, x), g(q, y), g(r, z))
    for p, q, r in product((-1, 1), repeat=3)
)
print(ans)


### FIXED CODE ###

from itertools import product
N, M = map(int, input().split())
x, y, z = zip(*(map(int, input().split()) for _ in range(N)))


def f(a, b, c):
    return sum(sorted(map(sum, zip(a, b, c)), reverse=True)[:M])


def g(k, a):
    return [k * e for e in a]


ans = max(
    f(g(p, x), g(q, y), g(r, z))
    for p, q, r in product((-1, 1), repeat=3)
)
print(ans)
### BUGGY CODE ###

#coding:utf-8

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

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

h = input().split()
H = [int(i) for i in h]

def check(lis,item):
    if item in lis:
        return True
    else:
        return False

for i in range(M):
    bol = False
    A,B = map(int,input().split())
    HA = H[A-1]
    HB = H[B-1]
    if HA > HB:
        bol = check(Observ,B)
        if bol:
            Observ.remove(B)
    elif HA < HB:
        bol = check(Observ,A)
        if bol:
            Observ.remove(A)
    elif HA == HB:
        bol = check(Observ,A)
        if bol:
            Observ.remove(A)
        bol = check(Observ,B)
        if bol:
            Observ.remove(B)

ans = len(Observ)
print("{}".format(ans))

### FIXED CODE ###

#coding:utf-8

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

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

h = input().split()
H = [int(i) for i in h]

for i in range(M):
    A,B = map(int,input().split())
    HA = H[A-1]
    HB = H[B-1]
    if HA > HB:
        Observ[B-1] = 0
    elif HA < HB:
        Observ[A-1] = 0
    elif HA == HB:
        Observ[A-1] = 0
        Observ[B-1] = 0

ans = 0
for i in Observ:
    ans += i
    
print("{}".format(ans))
### BUGGY CODE ###

from sys import stdin
import numpy as np
inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]

li = [["#" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]

def all_pairs_shortest_paths(W):
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

a = np.arange(h*w)
a = a.reshape([h,w])
a = a.tolist()

lin = [[0 for i in range(h*w)]for j in range(h*w)]

for i in range(h):
    for j in range(w-1):
        if li[i][j] == "." and li[i][j+1] == ".":
            lin[a[i][j]][a[i][j+1]] = 1
            lin[a[i][j+1]][a[i][j]] = 1

for i in range(h-1):
    for j in range(w):
        if li[i][j] == "." and li[i+1][j] == ".":
            lin[a[i][j]][a[i+1][j]] = 1
            lin[a[i][j]][a[i+1][j]] = 1

lis = all_pairs_shortest_paths(lin)

ma = 0
for i in range(h*w):
    for j in range(h*w):
        if lis[i][j] != 10**10:
            ma = max(lis[i][j],ma)

print(ma)

### FIXED CODE ###

from sys import stdin

inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]

li = [["#" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]

def all_pairs_shortest_paths(W):
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

a = [[0 for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        a[i][j] = i*w + j

lin = [[0 for i in range(h*w)]for j in range(h*w)]

for i in range(h):
    for j in range(w-1):
        if li[i][j] == "." and li[i][j+1] == ".":
            lin[a[i][j]][a[i][j+1]] = 1
            lin[a[i][j+1]][a[i][j]] = 1

for i in range(h-1):
    for j in range(w):
        if li[i][j] == "." and li[i+1][j] == ".":
            lin[a[i][j]][a[i+1][j]] = 1
            lin[a[i][j]][a[i+1][j]] = 1

lis = all_pairs_shortest_paths(lin)

ma = 0
for i in range(h*w):
    for j in range(h*w):
        if lis[i][j] != 10**10:
            ma = max(lis[i][j],ma)

print(ma)
### BUGGY CODE ###

import numpy as np
N,M=map(int,input().split())
A=np.zeros(N)
B=np.zeros([M,2])
for i in range(M):
  k,l=map(int,input().split())
  B[i,0]=k
  B[i,1]=l

C={1}
D=set()
E=[]
while len(C)<N:
  for i in range(B.shape[0]):
    if B[i,0] in C:
      if A[int(B[i,1])-1]==0:
        A[int(B[i,1])-1]=B[i,0]
        D.add(B[i,1])
      E.append(i)
    elif B[i,1] in C:
      if A[int(B[i,0])-1]==0:
        A[int(B[i,0])-1]=B[i,1]
        D.add(B[i,0])
      E.append(i)
  B=np.delete(B,E,0)
  E=[]
  C=C|D
  D=set()

print("Yes")
for i in range(1,N):
  print(int(A[i]))


### FIXED CODE ###

import queue
N,M=map(int,input().split())
ans=[0] * N
q=queue.Queue()
q.put(1)

import sys
s = sys.stdin.readlines()
G=[[] for _ in range(N)]

for e in s:
  a, b = map(int, e.split())
  G[a-1].append(b)
  G[b-1].append(a)
  
c=0

while c!=N-1:
  r=q.get()
  for i in G[r-1]:
    if ans[i-1]==0 and i!=1:
      ans[i-1]=r
      q.put(i)
      c+=1

print("Yes")
for i in range(N-1):
  print(ans[i+1])
### BUGGY CODE ###

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

for _ in range(M):
    A = sorted(A, reverse=True)
    if A[0] == 0:
        break
    A[0] //= 2

print(sum(A)) 

### FIXED CODE ###

import heapq as hq

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
que = []
for i, a in enumerate(A):
    hq.heappush(que, (-a, str(i))) 

for _ in range(M):    
    priority, a = hq.heappop(que)    
    if priority == 0:
        break
    priority = - priority
    priority //= 2
    hq.heappush(que, (-priority, a))

sum_ = 0
for q in que:
    sum_ += q[0]

print(-sum_)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
  w[i], v[i] = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=int)
for i in range(1, N+1):
  for sum_w in range(1, W+1):
    if sum_w - w[i-1] >= 0:
      dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w[i-1]] + v[i-1])
    dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
print(dp[N][W])

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack():
  dp = np.zeros((N+1, W+1), dtype=int)
  c = np.arange(1, N+1)
  for i in c:
    w, v = map(int, input().split())
    dp[i][w:] = np.maximum(dp[i-1][w:], dp[i-1][:-w] + v)
    dp[i][:] = np.maximum(dp[i][:], dp[i-1][:])
  return dp[-1][-1]
print(knapsack())
### BUGGY CODE ###

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

def dfs(h, w, count=0):
    if s[h][w]=='#':
        count+=1
    if h==H-1 and w==W-1:
        return count
    else:
        ans = float('inf')
        if w+1<W:
            ans = min(ans, dfs(h, w+1, count=count))
            if ans == 0:
                return 0
        if h+1<H:
            ans = min(ans, dfs(h+1, w, count=count))
            if ans == 0:
                return 0
        return ans
print(dfs(0,0,0))

### FIXED CODE ###

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

dp = [[float('inf')]* W for _ in range(H)]

if s[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

for c in range(W):
    for r in range(H):
        if r > 0:
            count=0
            if s[r-1][c]=='.' and s[r][c]=='#':
                count = 1
            dp[r][c] = min(dp[r][c], dp[r-1][c]+count)
        if c > 0:
            count=0
            if s[r][c-1]=='.' and s[r][c]=='#':
                count = 1
            dp[r][c] = min(dp[r][c], dp[r][c-1]+count)
print(dp[H-1][W-1])
### BUGGY CODE ###

from queue import Queue

N, Q = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

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

searched = [False for _ in range(N+1)]
searched[1] = True
q = Queue()

def bfs(i, add_point):
    if i > N:
        return
    if searched[i]:
        return
    searched[i] = True
    score[i] += add_point
    q.put([i, score[i]])
    return
    
q.put([1, score[1]])
    
while not q.empty():
    i, p = q.get()
    for j in adj[i]:
        bfs(j, p)

print(" ".join(map(str, score[1:])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
from queue import Queue

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

N, Q = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

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

def dfs(now, prev):
    for target in adj[now]:
        if target == prev:
            continue
        score[target] += score[now]
        dfs(target, now)

dfs(1, 0)

print(" ".join(map(str, score[1:])))
### BUGGY CODE ###

from collections import deque

N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]

key_order = [0] * (N-1)
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    key_order[i] = (in1, in2)

# [print(i, t) for i, t in enumerate(tree)]


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))

    node_colors = [set() for _ in tree]
    edge_colors = dict()
    all_colors = set()
    color = 0

    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True
        for v in tree[q]:
            if not seen[v]:
                residual = all_colors - node_colors[q]
                if len(residual) > 0:
                    this_color = min(residual)
                else:
                    color += 1
                    this_color = color
                edge_colors[(q, v)] = this_color
                node_colors[q].add(this_color)
                node_colors[v].add(this_color)
                all_colors.add(this_color)

                queue.append(v)

    return edge_colors


edge_colors = bfs(tree, 0)

print(max([c for key, c in edge_colors.items()]))
[print(edge_colors[t]) for t in key_order]
# print(edge_colors)

# show_tree(tree)


### FIXED CODE ###

from collections import deque

N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]

key_order = [0] * (N-1)
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    key_order[i] = (in1, in2)

# [print(i, t) for i, t in enumerate(tree)]


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))

    edge_colors = dict()
    node_colors = [0] * len(tree)
    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        parent_color = node_colors[q]

        cnt = 1
        for v in tree[q]:
            if not seen[v]:
                if cnt == parent_color:
                    cnt += 1

                edge_colors[(q, v)] = cnt
                node_colors[v] = cnt
                queue.append(v)
                cnt += 1



    """
    node_colors = [set() for _ in tree]
    edge_colors = dict()
    all_colors = set()
    color = 0

    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        for v in tree[q]:
            if not seen[v]:
                residual = all_colors - node_colors[q]
                if len(residual) > 0:
                    this_color = residual.pop()
                else:
                    color += 1
                    this_color = color
                edge_colors[(q, v)] = this_color
                node_colors[q].add(this_color)
                node_colors[v].add(this_color)
                all_colors.add(this_color)

                queue.append(v)
    """

    return edge_colors


edge_colors = bfs(tree, 0)

print(max([c for key, c in edge_colors.items()]))
[print(edge_colors[t]) for t in key_order]
# print(edge_colors)

# show_tree(tree)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    N = int(input())

    # Initialize
    l, r = 0, N - 1
    print(l)
    sl = input().rstrip()
    print(r)
    sr = input().rstrip()
    if sl == "Vacant" or sr == "Vacant":
        exit()

    for _ in range(18):
        mid = (l + r) // 2
        print(mid)
        s = input().rstrip()
        if s == "Vacant":
            exit()
        if (mid - l) % 2 == 0:
            if sl == s:
                l = mid
            else:
                r = mid
        else:
            if sl == s:
                r = mid
            else:
                l = mid


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    N = int(input())

    # Initialize
    l, r = 0, N - 1
    print(l, flush=True)
    sl = input().rstrip()
    print(r, flush=True)
    sr = input().rstrip()
    if sl == "Vacant" or sr == "Vacant":
        exit()

    for _ in range(18):
        mid = (l + r) // 2
        print(mid, flush=True)
        s = input().rstrip()
        if s == "Vacant":
            exit()
        if (mid - l) % 2 == 0:
            if sl == s:
                l = mid
                sl = s
            else:
                r = mid
                sr = s
        else:
            if sl == s:
                r = mid
                sr = s
            else:
                l = mid
                sl = s


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

import itertools
N, M, R = map(int, input().split())
r = tuple(map(lambda n: int(n)-1, input().split()))
inf = float("inf")
vertices = [[inf]*N for _ in [0]*N]
for _ in [0]*M:
    a, b, c = map(int, input().split())
    vertices[a-1][b-1] = c
    vertices[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        c2 = vertices[i][k]
        for j, (c1, c3) in enumerate(zip(vertices[i], vertices[k])):
            vertices[i][j] = c1 if c1 < c2+c3 else c2+c3

ans = inf

for p in itertools.permutations(r):
    subt = 0
    for i in range(R-1):
        subt += vertices[p[i]][p[i+1]]
    if subt < ans:
        ans = subt

print(ans)


### FIXED CODE ###

import itertools
N, M, R = map(int, input().split())
r = tuple(map(lambda n: int(n)-1, input().split()))
inf = float("inf")
vertices = [[inf]*N for _ in [0]*N]
for _ in [0]*M:
    a, b, c = map(int, input().split())
    vertices[a-1][b-1] = c
    vertices[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        c2 = vertices[i][k]
        for j, (c1, c3) in enumerate(zip(vertices[i], vertices[k])):
            vertices[i][j] = c1 if c1 < c2+c3 else c2+c3

ans = inf

for p in itertools.permutations(r):
    subt = 0
    for i in range(R-1):
        subt += vertices[p[i]][p[i+1]]
    if subt < ans:
        ans = subt

print(ans)