import heapq
INF = int(1e9)
n, m, r = map(int, input().split())
t = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(r):
a, b, c = map(int, input().split())
g[a-1].append((b-1, c))
g[b-1].append((a-1, c))
def dijkstra(s):
d = [INF] * n
q = []
heapq.heappush(q, (0, s))
d[s] = 0
while q:
dist, now = heapq.heappop(q)
if d[now] < dist:
continue
for y, ndist in g[now]:
cost = dist + ndist
if d[y] >= cost:
d[y] = cost
heapq.heappush(q, (cost, y))
return d
ans = 0
for i in range(n):
dist = dijkstra(i)
items = 0
for i, d in enumerate(dist):
if d <= m:
items += t[i]
ans = max(ans, items)
print(ans)
다익스트라로 최단거리를 탐색해서 그 중 탐색 가능한 곳에서 얻을 수 있는 아이템의 수의 최대값 구함
플로이드 와샬도 가능해보임