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

# -*- coding utf-8 -*-
import copy

MOD = 10 ** 9 + 7

n = int(input())
uvw_n = [list(map(int, input().split())) for _ in range(n - 1)]

graph = [[-1] * n for _ in range(n)]
for u, v, w in uvw_n:
    graph[u - 1][v - 1] = w
    graph[v - 1][u - 1] = w

# print(graph)

root = 0
dist = [-1] * (n)
new = {0}
while len(new) != 0:
    next_new = set()
    for i in new:
        for j in range(n):
            if dist[j] == -1 and graph[i][j] != -1:
                dist[j] = dist[i] + graph[i][j]
                next_new.add(j)
    # print(next_new)
    new = next_new

for d in dist:
    print(d % 2)



### FIXED CODE ###

# -*- coding utf-8 -*-

MOD = 10 ** 9 + 7

n = int(input())

graph = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u - 1].append((v - 1, w))
    graph[v - 1].append((u - 1, w))

dist = [-1] * n
dist[0] = 0
que = [0]
while len(que) != 0:
    i = que.pop()
    for j, w in graph[i]:
        if dist[j] == -1:
            dist[j] = dist[i] + w
            que.append(j)

for d in dist:
    print(d % 2)
### BUGGY CODE ###

from math import gcd
K=int(input())
if K%7==0:
  K=K//7
if gcd(10,K)!=1:
  print(-1)
  exit
x=1%K
cnt=1
while x!=0:
  x=(10*x+1)%K
  cnt+=1
print(cnt)

### FIXED CODE ###

K = int(input())
x = 7 % K #mod(K)
if K == 1 or K == 7:
  print(1)
  exit()
ans = 1
i = 0
while i < K:
  ans += 1
  x = (x * 10 + 7) % K
  
  
  if x == 0:
    print(ans)
    exit()
  i += 1
print('-1')
### BUGGY CODE ###

import sys
import collections
import math
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = dict(collections.Counter(a))
    for i in range(n):
        ans = 0
        cnt[a[i]] -= 1
        for j in cnt.values():
            if j >= 2:
                ans += math.factorial(j)//(2*math.factorial(j-2))
        cnt[a[i]] += 1
        print(ans)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import collections
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = collections.Counter(a)
    all_comb = 0
    for i in cnt.keys():
        all_comb += cnt[i] * (cnt[i]-1) // 2
    for i in range(n):
        comb = all_comb
        comb -= cnt[a[i]] * (cnt[a[i]]-1) // 2
        comb += (cnt[a[i]]-1) * (cnt[a[i]]-2) // 2
        print(comb)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
alist = list(map(int, input().split()))

for i in range(1,n+1):
  print(alist.count(i))

### FIXED CODE ###

n = int(input())
alist = list(map(int, input().split(" ")))
dp = [0]*n

for i in alist:
  dp[i-1]+=1

for i in dp:
  print(int(i))
### BUGGY CODE ###

a = input()
a = input().split()
a = [int(i) for i in a]
# print(a)

cnt = 0
while a:
    num = 0
    for i in a:
        num += i
        if num == 0:
            cnt += 1
    a.pop(0)

print(cnt)


### FIXED CODE ###

import numpy
from collections import Counter

_ = input()
a = numpy.array(list(map(int, input().split())))

s = numpy.cumsum(a)
s = numpy.concatenate(([0], s))
ans = 0

for i in Counter(s).values():
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
S = map(int,raw_input().split())
q = int(input())
T = map(int,raw_input().split())
count = 0
lst = []
for v in S:
    if v in lst:
        pass
    else:
        for i in range(q):
            if T[i] == v:
                count += 1
    lst.append(v)
print count

### FIXED CODE ###

n = int(input())
S = set(raw_input().split())
q = int(input())
T = set(raw_input().split())
print len(S&T)
### BUGGY CODE ###

def gcd(x, y):
    if x < y:
        x, y = y, x
    if y < 1:
        return x
    return gcd(y, x%y)

k = int(input())

sum = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        gcd_ab = gcd(a, b)
        for c in range(1, k+1):
            sum += gcd(gcd_ab, c)

print(sum)

### FIXED CODE ###

def gcd(x, y):
    if x < y:
        x, y = y, x
    while y != 0:
        org_x = x
        x = y
        y = org_x % y
    return x

k = int(input())

sum = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        gcd_ab = gcd(a, b)
        for c in range(1, k+1):
            sum += gcd(gcd_ab, c)

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

N = int(input())
X = list(input())
X = [int(x) for x in X]
popcnt = 0
for i in range(N):
    if X[i]:
        popcnt += 1

for i in range(N):
    if X[i]:#1->0
        mod = popcnt-1
    else:#0->1
        mod = popcnt+1

    if mod == 0:
        print(0)
        continue

    tmpX = X[:]
    tmpX[i] ^= 1

    Y = 0
    ans = 1
    for j in range(N):
        if tmpX[N-1-j]:
            Y += pow(2,j,mod)
            Y %= mod
    # print(Y,mod)
    if Y == 0:
        print(ans)
        continue
        
    while Y > 0:
        L = Y.bit_length()
        mod = 0
        for j in range(L):
            if Y>>j&1:
                mod += 1
        Y %= mod
        ans += 1
    print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]

    if Xc == 0:
        [print(1) for i in range(N)]
    elif Xc == 1:
        d = X.index(1)
        ans1 = 0
        for j in range(N):
            if X[j]:
                ans1 += pow(2,N-1-j,Xc+1)
                ans1 %= Xc+1

        for j in range(N):
            if d == j:
                print(0)
            else:
                if d == N-1 or j == N-1:
                    print(2)
                else:
                    print(1)
    else:
        ans1 = 0
        ans2 = 0
        for j in range(N):
            if X[j]:
                ans1 += pow(2,N-1-j,Xc+1)
                ans1 %= Xc+1
                ans2 += pow(2,N-1-j,Xc-1)
                ans2 %= Xc-1

        for i in range(N):
            if X[i]:# 1->0
                ans = (ans2 - pow(2,N-1-i,Xc-1)) % (Xc-1)
            else:# 0->1
                ans = (ans1 + pow(2,N-1-i,Xc+1)) % (Xc+1)
            count = 1
            while ans > 0:
                tmp = str(bin(ans)).count('1')
                ans %= tmp
                count += 1
            print(count)

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

S = input()
N = len(S)
C = [0 for i in range(2019)]
C[0] = 1
now = 0
for i in range(N):
    now += int(S[-i-1])*(10**i)
    now %= 2019
    C[now] += 1
ans = 0
for i in range(2019):
    ans += C[i]*(C[i]-1)//2
print(ans)



### FIXED CODE ###

S = input()
N = len(S)
C = [0 for i in range(2019)]
C[0] = 1
now = 0
tenfactor = 1

for i in range(N):
    s = int(S[-i-1])
    now = (now + s*tenfactor)%2019
    tenfactor = tenfactor*10%2019
    C[now] += 1
ans = 0
for i in range(2019):
    ans += C[i]*(C[i]-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
X = tuple(map(int, input().split()))

for i in range(N):
    Y = list(X)
    del Y[i]
    Y.sort()
    print(Y[N//2-1])


### FIXED CODE ###

N = int(input())
X = tuple(map(int, input().split()))

Y = list(X)
Y.sort()

greater_median = Y[N//2]
smaller_median = Y[N//2-1]
average = (greater_median + smaller_median)/2

for x in X:
    if x <= average:
        print(greater_median)
    else:
        print(smaller_median)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def solve():
    maxV = 12800

    H, W = map(int, input().split())
    Ass = [tuple(map(int, input().split())) for _ in range(H)]
    Bss = [tuple(map(int, input().split())) for _ in range(H)]

    dp = [[[0]*(2*maxV+1) for j in range(W)] for i in range(H)]
    diff = abs(Ass[0][0] - Bss[0][0])
    dp[0][0][diff+maxV] = dp[0][0][-diff+maxV] = 1
    for i in range(H):
        for j in range(W):
            diff = abs(Ass[i][j] - Bss[i][j])
            if i > 0:
                dp0 = dp[i-1][j]
                dpij = dp[i][j]
                for k in range(diff, 2*maxV+1):
                    if dp0[k]:
                        dpij[k-diff] = 1
                for k in range(2*maxV+1-diff):
                    if dp0[k]:
                        dpij[k+diff] = 1
            if j > 0:
                dp0 = dp[i][j-1]
                dpij = dp[i][j]
                for k in range(diff, 2*maxV+1):
                    if dp0[k]:
                        dpij[k-diff] = 1
                for k in range(2*maxV+1-diff):
                    if dp0[k]:
                        dpij[k+diff] = 1

    ans = maxV
    dpHW = dp[-1][-1]
    for k in range(2*maxV+1):
        if dpHW[k]:
            j = abs(k-maxV)
            if j < ans:
                ans = j

    print(ans)


solve()


### FIXED CODE ###

maxV = 80*(80+80)

H, W = map(int, input().split())
Ass = [tuple(map(int, input().split())) for _ in range(H)]
Bss = [tuple(map(int, input().split())) for _ in range(H)]

dp = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        A, B = Ass[i][j], Bss[i][j]
        if A > B:
            A, B = B, A
        if i == 0 and j == 0:
            dp[i][j] = 1<<(maxV+B-A) | 1<<(maxV-B+A)
        if i > 0:
            dp[i][j] |= dp[i-1][j]<<(B-A) | dp[i-1][j]>>(B-A)
        if j > 0:
            dp[i][j] |= dp[i][j-1]<<(B-A) | dp[i][j-1]>>(B-A)

bitset = dp[-1][-1]
mask = 1<<(2*maxV)
ans = maxV
for i in range(-maxV, maxV+1):
    if bitset & mask:
        ans = min(ans, abs(i))
    mask >>= 1

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

# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
q=deque()
q.append(N)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in rev_al[fro]:
		if Visit[to]==0:
			q.append(to)
			
Visit1=Visit

#スタートからBFS
q=deque()
q.append(1)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to]==0:
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)


D=[ float("-inf") for _ in range(N+1) ]	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード N-1回
for _ in range(N-1):
	for a,b,c in edge:
		if V[a]==1 and V[b]==1:
			D[b]=max( D[b],D[a]+c )

D1=copy.deepcopy(D)

#ベルマンフォード 追加1回で差分gが出たら閉路検出
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		D[b]=max( D[b],D[a]+c )

if D1!=D:
	print -1
else:
	print max(D[N],0)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit

#スタートからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") ]*(N+1)	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])
### BUGGY CODE ###

s=input()
K=int(input())

dic={}
for i in range(len(s)):
    dic[s[i:]]=1
arr=sorted(dic)
dic={}
for x in arr:
    for i in range(0,len(x)):
        tmp = x[:i+1]
        if dic.get(tmp,0)==0:
            K-=1
            dic[tmp]=1
        else:
            continue
        if K==0:
            print(x[:i+1])

### FIXED CODE ###

s=input()
K=int(input())

dic={}
for i in range(len(s)):
    dic[s[i:]]=1
arr=sorted(dic)
dic={}

for x in arr:
    for i in range(0,len(x)):
        tmp = x[:i+1]
        if dic.get(tmp,0)==0:
            K-=1
            dic[tmp]=1
        else:
            continue
        if K==0:
            print(x[:i+1])
            break
    if K<0:
        break
### BUGGY CODE ###

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

for i in range(M):
    A = sorted(A)
    A[-1] = A[-1] // 2

print(sum(A))

### FIXED CODE ###

import heapq

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

for i in range(len(A)):
    A[i] *= -1

heapq.heapify(A)
for _ in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A, (-x//2)*(-1))

print(-sum(A))
### BUGGY CODE ###

import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

    for i in range(Q):
        l, r = map(int, input().split())
        E.append((l - 1, r - 1, i))

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    ANS = [0] * Q
    y_list = []
    for e in E:
        if e[2] == -1:
            y_list.append(e[1])
        else:
            y_list.sort()
            ans = bisect.bisect_right(y_list, e[1])
            ANS[e[2]] = e[1] - e[0] + 1 - ans

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

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

stepper = 0
gate = []

for j in range(M):
    gate_1, gate_2 = map(int, input().split())
    gate.append([gate_1, gate_2])


def judge(num):
    num += 1
    counter = 0
    for k in gate:
        if k[0] <= num <= k[1]:
            counter += 1
    if counter == M:
        return 1
    else:
        return 0


for ans in map(judge, range(N)):
    stepper += ans
print(stepper)
"""
for i in range(N):
    i += 1
    counter = 0
    for k in gate:
        #print(k, i)
        if k[0] <= i <= k[1]:
            counter += 1
    #print(counter, M)
    if counter == M:
        stepper += 1
"""


### FIXED CODE ###

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

stepper = 0
gate = []

for j in range(M):
    gate_1, gate_2 = map(int, input().split())
    gate.append([gate_1, gate_2])

gate_min = 0
gate_max = N

for m in range(M):
    if gate[m][0] > gate_min:
        gate_min = gate[m][0]

    if gate[m][1] < gate_max:
        gate_max = gate[m][1]

#print(gate_min, gate_max)
for k in range(N):
    k = k+1
    if gate_min <= k <= gate_max:
        stepper += 1

print(stepper)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [-1] * m
c = [-1] * m
a.sort()
for j in range(m):
    b[j], c[j] = map(int, input().split())
    count = 0
    for i in range(n):
        if count >= b[j]:
            break
        if a[i] > c[j]:
            break
        if a[i] < c[j]:
            count += 1
    index = n
    for i in range(n):
        if a[i] >= c[j]:
            index = i
            break
    for i in range(count):
        a.insert(index, c[j])
    for i in range(count):
        del a[0]

print(sum(a))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = [tuple(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda t: t[1], reverse=True)

index = 0
count = [0] * m
for i in range(n):
    if index >= m or a[i] >= bc[index][1]:
        break
    a[i] = bc[index][1]
    count[index] += 1
    if count[index] >= bc[index][0]:
        index += 1

print(sum(a))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)

def main():
    ii = lambda: int(input())
    mis = lambda: map(int, input().split())
    lmis = lambda: list(mis())

    N, M, P = mis()

    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = [(a, b, c) for a, b, c in edges if a in ok and b in ok]

    V = [float('inf')] * N
    V[0] = 0

    def bf_step():
        for a, b, c in edges:
            V[b] = min(V[b], V[a] + c)

    def bf():
        for _ in range(N):
            bf_step()

    bf()

    Vb = tuple(V)
    bf_step()

    if tuple(V) == Vb:
        print(max(-V[-1], 0))
    else:
        print(-1)

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()
### BUGGY CODE ###

from itertools import permutations


class Solve():
    def __init__(self):
        self.N, self.M, self.R = map(int, input().split())
        self.r = list(map(int, input().split()))
        self.route = [[float('inf') for _ in range(self.N)] for _ in range(self.N)]
        for _ in range(self.M):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c

    def WFInitialize(self):
        self.dist = [[float('inf') for _ in range(self.N)] for _ in range(self.N)]
        for i in range(self.N):
            for j in range(self.N):
                if self.dist[i][j] is not float('inf'):
                    self.dist[i][j] = self.route[i][j]
        for i in range(self.N):
            self.dist[i][i] = 0

    def WarshallFloid(self):
        self.WFInitialize()
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    if self.dist[i][j] > self.dist[i][k] + self.dist[k][j]:
                        self.dist[i][j] = self.dist[i][k] + self.dist[k][j]

    def execute(self):
        self.WarshallFloid()
        ans = float('inf')
        perm = permutations(self.r)
        for path in perm:
            temp = 0
            for i in range(self.R - 1):
                temp += self.dist[path[i] - 1][path[i + 1] - 1]
            ans = min(ans, temp)
        print(ans)


if __name__ == '__main__':
    Solve().execute()

### FIXED CODE ###

from itertools import permutations
class Solve():
    def __init__(self):
        self.N, self.M, self.R = map(int, input().split())
        self.r = list(map(int, input().split()))
        self.route = [[float('inf') for _ in range(self.N)] for _ in range(self.N)]
        for _ in range(self.M):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        for i in range(self.N):
            self.route[i][i] = 0

    def WarshallFloid(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    if self.route[i][j] > self.route[i][k] + self.route[k][j]:
                        self.route[i][j] = self.route[i][k] + self.route[k][j]

    def execute(self):
        self.WarshallFloid()
        ans = float('inf')
        checked = set()
        for path in permutations(self.r):
            if tuple(reversed(path)) in checked:
                continue
            checked.add(tuple(reversed(path)))
            temp = 0
            for i in range(self.R - 1):
                temp += self.route[path[i] - 1][path[i + 1] - 1]
            ans = min(ans, temp)
        print(ans)


if __name__ == '__main__':
    Solve().execute()