import sys readline=sys.stdin.readline import heapq class Graph: def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")): self.V=V self.directed=directed self.weighted=weighted self.inf=inf if not graph: self.edges=edges self.graph=[[] for i in range(self.V)] if weighted: for i,j,d in self.edges: self.graph[i].append((j,d)) if not self.directed: self.graph[j].append((i,d)) else: for i,j in self.edges: self.graph[i].append(j) if not self.directed: self.graph[j].append(i) else: self.graph=graph self.edges=[] for i in range(self.V): if self.weighted: for j,d in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j,d)) else: for j in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j)) def Dijkstra(self,s,route_restoration=False): dist=[self.inf]*self.V dist[s]=0 hq=[(0,s)] if route_restoration: parents=[None]*self.V while hq: dx,x=heapq.heappop(hq) if dist[x]dx+dy: dist[y]=dx+dy if route_restoration: parents[y]=x heapq.heappush(hq,(dist[y],y)) if route_restoration: return dist,parents else: return dist N,M,L=map(int,readline().split()) L-=1 T=list(map(int,readline().split())) edges=[] for _ in range(M): a,b,c=map(int,readline().split()) a-=1;b-=1 edges.append((a,b,c)) inf=1<<40 G=Graph(N,edges=edges,weighted=True,inf=inf) dist=[G.Dijkstra(i) for i in range(N)] ans=inf for i in range(N): s=sum(T[j]*dist[i][j] for j in range(N))*2 if s: s+=min(dist[L][j]-dist[i][j] for j in range(N) if T[j]) ans=min(ans,s) print(ans)