from queue import PriorityQueue

N,M,L = list(map(int, input().split(' ')))
T = list(map(int, input().split(' ')))

E = []
for _ in range(N):
    E.append([])

for _ in range(M):
    a,b,c = list(map(int, input().split(' ')))
    E[a-1].append((b-1,c))
    E[b-1].append((a-1,c))

D = []
for _ in range(N):
    D.append([float('inf') for _ in range(N)])
    
for i in range(N):
    D[i][i] = 0
    
    que = PriorityQueue()
    que.put((0,i))
    while not que.empty():
        cost,current = que.get()
        if D[i][current] != cost:
            continue
        for e in E[current]:
            if D[i][current] + e[1] < D[i][e[0]]:
                D[i][e[0]] = D[i][current] + e[1]
                que.put((D[i][e[0]], e[0]))

answer = float('inf')                
for i in range(N):
    start = float('inf')    
    total = 0
    for j in range(N):
        if T[j]:
            total = total + T[j] * D[i][j] * 2
            start = min(start, D[L][j] - D[j][i])
    answer = min(answer, start + total)

print(answer)