#include <iostream>
#include <algorithm>
#include <vector>

#define INF 10000000

using namespace std;


class Graph {
public:
    int n;
    vector<pair<int, int>>* adj;
    int *nItems; // 정점에서 얻을 수 잇는 아이템수

    Graph(int n) {
        this->n = n;
        adj = new vector<pair<int, int>>[n + 1];
        nItems = new int[n + 1];
        nItems[0] = 0;
    }

    // 간선 추가
    void insertEdge(int u, int v, int w) {
        this->adj[u].push_back(make_pair(v, w));
        this->adj[v].push_back(make_pair(u, w));
    }

    // 정점 v에서 얻을 수 있는 아이템 수 설정
    void setNItems(int v, int n) {
        nItems[v] = n;
    }
};

void input(Graph* g, int nVertices, int nEdges) {
    for (int i = 1; i < nVertices + 1; i++) {
        int nItems;
        cin >> nItems;
        g->setNItems(i, nItems);
    }

    for (int i = 0; i < nEdges; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        g->insertEdge(u, v, w);
    }
}


// N[i][j] : i에서 출발해 탬색 범위 내의 j에서 얻을 수 있는 아이템 수
int solve(Graph* g, int range) {
    int** A = new int*[(g->n) + 1];
    int** N = new int* [(g->n) + 1];

    for (int i = 0; i < g->n + 1; i++) {
        A[i] = new int[(g->n) + 1];
        N[i] = new int[(g->n) + 1];
    }

    // 기본값 A에서 자신에 대해 0, 아닌경우는 INF로 초기화 하고
    for (int i = 0; i < g->n + 1; i++) {
        for (int j = 0; j < g->n + 1; j++) {
            N[i][j] = 0;
            if (i == j) {
                A[i][j] = 0;
            }
            else {
                A[i][j] = INF;
            }
        }
    }

    // 처음 알 수 있는 인접정점에 대해 A를 업데이트 한다.
    for (int i = 0; i < g->n + 1; i++) {
        N[i][i] = g->nItems[i];

        int s = g->adj[i].size();
        for (int j = 0; j < s; j++) {
            pair<int, int> v = g->adj[i][j];

            // 인접 정점이 탐색 범위 내에 있는 경우만
            if (v.second <= range) {
                A[i][v.first] = v.second;
                N[i][v.first] = g->nItems[v.first];
            }
        }
    }


    // Floyd Warshall
    for (int k = 0; k < g->n + 1; k++) {
        for (int i = 0; i < g->n + 1; i++) {
            for (int j = 0; j < g->n + 1; j++) {
                int newPath = A[i][k] + A[k][j];
                // 새로 구해진 정점 k를 거쳐 가는 최단 거리가 탐색 범위 내인 경우만
                if (newPath < A[i][j] && newPath <= range) {
                    A[i][j] = newPath; // A 업데이트
                    N[i][j] = g->nItems[j]; // i에서 출발했을때 j에서 얻는 아이템수
                }
            }
        }
    }
    

    // i에서 출발한 탐색범위 내의 j에서 얻을 수 있는 아이템수를 다 더한다.
    // 그후 가장 많이 얻을 수 있는 아이템의 수를 찾는다.
    int res = -0x7fffffff;
    for (int i = 0; i < g->n + 1; i++) {
        int sum = 0;

        // 정점 i시작 한 경우 얻을 수 있는 아이템수 합
        for (int j = 0; j < g->n + 1; j++) {
            if (N[i][j] != 0) {
                sum += N[i][j];
            }
        }

        // 가장 큰 값을 찾는다.
        res = max(res, sum);
    }

    // 결과 res
    return res;
}


int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    // 정점 수, 탐색 범위, 간선 수 입력
    int nVertices, range, nEdges;
    cin >> nVertices >> range >> nEdges;

    // 그래프 생성
    Graph* g = new Graph(nVertices);

    // 입력
    input(g, nVertices, nEdges);

    // 결과 출력
    cout << solve(g, range);

    return 0;
}