import sys,random input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) N,M,K = mi() A = li() dist = [[10**17 for j in range(N)] for i in range(N)] for i in range(N): dist[i][i] = 0 for i in range(M): x,y,z = mi() dist[x-1][y-1] = min(dist[x-1][y-1],z) dist[y-1][x-1] = min(dist[y-1][x-1],z) for k in range(N): for i in range(N): for j in range(N): if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] dp = [float("inf") for i in range(1<<N)] dp[0] = 0 for S in range(2**N-1): for i in range(N): if S>>i & 1 == 0: cost = A[i] if S!=0: D = min(dist[i][k] for k in range(N) if S>>k & 1) cost += D dp[S+2**i] = min(dp[S+2**i],dp[S]+cost) res = float("inf") for S in range(2**N): cnt = sum(1 for i in range(N) if S>>i & 1) if cnt==K: res = min(res,dp[S]) print(res)