@staticmethod
def d():
    (n, m, t) = map(int, sys.stdin.readline().split())
    point = np.array(sys.stdin.readline().split(), dtype=int)
    (a, b, c) = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(m, 3).T
    a -= 1
    b -= 1
    d_1 = shortest_path(csr_matrix((c, (a, b)), (n, n)), method='D', directed=True, indices=0)
    d_2 = shortest_path(csr_matrix((c, (b, a)), (n, n)), method='D', directed=True, indices=0)
    print(int(np.amax(((t - (d_1 + d_2)) * point))))
@staticmethod
def d():
    (n, m, t) = map(int, sys.stdin.readline().split())
    point = np.array(sys.stdin.readline().split(), dtype=int)
    (a, b, c) = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(m, 3).T
    a -= 1
    b -= 1
    d_1 = shortest_path(csr_matrix((c, (a, b)), (n, n)), method='D', directed=True, indices=0)
    d_2 = shortest_path(csr_matrix((c, (b, a)), (n, n)), method='D', directed=True, indices=0)
    print(int(np.amax(((t - (d_1 + d_2)) * point))))