from itertools import combinations
from atcoder.dsu import DSU
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
XYZ = [list(map(int,input().split())) for _ in range(M)]
INF = 10 ** 11
cost = [[INF] * N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0
for x,y,z in XYZ:
    x -= 1
    y -= 1
    cost[x][y] = z
    cost[y][x] = z
for k in range(N):
    for i in range(N):
        for j in range(N):
            if cost[i][k]!=INF and cost[k][j]!=INF:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
Q = []
for i in range(N):
    for j in range(i+1,N):
        Q.append((cost[i][j],i,j))
Q.sort()

ans = INF
for C in combinations(range(N),K):
    tmp = 0
    C = set(C)
    for c in C:
        tmp += A[c]
    dsu = DSU(N)
    cnt = 0
    for c,a,b in Q:
        if a in C and b in C:
            if dsu.same(a,b):
                continue
            dsu.merge(a,b)
            tmp += c
            cnt += 1
            if cnt == K:
                break
    ans = min(ans,tmp)

print(ans)