ㅅㄱ그라운드) python

#플로이드 워셔 알고리즘

def FloydWarshall(cost):
    n = len(cost)
    for i in range(n): cost[i][i] = 0    #자기 자신의 거리는 0
    for k in range(n):                    
        for i in range(n):

             #n*n 동안, j는 n의 범위 내에서, cost[i][j]는 cost[i][j]와, cost[i][k]+cost[k][j] 중 하나로 결정 됨. 더 작은 값으로. 배열의 거리 총 재정렬
            for j in range(n): cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

 

#메인함수 시작
n, m, r = map(int,input().split())
cost = [[float('inf')]*n for i in range(n)]   #요소가 양의 무한대인, n개 있는 1차 리스트, 그것이 또 n개가 있다.

#즉 2차원 리스트의 요소가 전부 양의 무한대

item = list(map(int,input().split()))
for i in range(r):                                #range(r)의 범위에서
    a, b, c = map(int,input().split())
    cost[a-1][b-1] = min(cost[a-1][b-1], c)    #cost[a-1][b-1]는, inf 또는 c가 될 것(이중 작은 것으로)
    cost[b-1][a-1] = min(cost[b-1][a-1], c)    

 

FloydWarshall(cost)  

maxi = 0

 

#i에서 n까지, maxi는 maxi와, item[j]의 범위 내에서, cost[i][j]가 m(수색범위)보다 작을 때의 item 중 작은값으로 갱신
for i in range(n): 

    maxi = max(maxi, sum(item[j] for j in range(n) if cost[i][j] <= m))
print(maxi)