import heapq def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]); idx +=1 M = int(data[idx]); idx +=1 L = int(data[idx]); idx +=1 t = list(map(int, data[idx:idx+N])); idx +=N adj = [[] for _ in range(N+1)] for _ in range(M): a = int(data[idx]); idx +=1 b = int(data[idx]); idx +=1 c = int(data[idx]); idx +=1 adj[a].append((b, c)) adj[b].append((a, c)) def dijkstra(start, n): dist = [float('inf')] * (n+1) dist[start] = 0 heap = [] heapq.heappush(heap, (0, start)) while heap: current_dist, u = heapq.heappop(heap) if current_dist > dist[u]: continue for v, w in adj[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w heapq.heappush(heap, (dist[v], v)) return dist d_L = dijkstra(L, N) global_min = float('inf') for X in range(1, N+1): d_x = dijkstra(X, N) sum_part = 0 for i in range(1, N+1): if t[i-1] > 0: sum_part += 2 * d_x[i] * t[i-1] min_candidate = float('inf') for i in range(1, N+1): if t[i-1] > 0: current = d_L[i] - d_x[i] if current < min_candidate: min_candidate = current total = sum_part + min_candidate if total < global_min: global_min = total print(global_min) if __name__ == "__main__": main()