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 self.graph=graph 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())) graph=[[] for i in range(N)] for _ in range(M): a,b,c=map(int,readline().split()) a-=1;b-=1 graph[a].append((b,c)) graph[b].append((a,c)) inf=1<<60 G=Graph(N,graph=graph,weighted=True,inf=inf) dist=[G.Dijkstra(i) for i in range(N)]