#include<iostream>
#include<algorithm>
#include<queue>
#include<deque>
using namespace std;
typedef long long ll;
#define re register
typedef pair<ll, int> pii;
const int max_n = 1e4 + 100;
const int max_m = 5e4 + 100;
const ll inf = 1e18;
struct edge{
    int to, cost, next;
}E[max_m * 2];
int head[max_n];
int cnt = 1;
inline void add(int from,int to,int cost) {
    E[cnt].to = to;
    E[cnt].cost = cost;
    E[cnt].next = head[from];
    head[from] = cnt++;
}
int n, m, t;

int cs[max_n];

struct eedge{
    int to, next;
}EE[max_m];
int head2[max_n];
int ccnt = 1;
inline void add2(int from,int to) {
    EE[ccnt].to = to;
    EE[ccnt].next = head2[from];
    head2[from] = ccnt++;
}

ll dist[max_n];
int fa[max_n];
inline void dijstra(int s) {
    fill(dist, dist + n + 1, inf);
    dist[s] = 0;
    priority_queue<pii> que;
    que.push({ dist[s],s });
    while (!que.empty()) {
        pii p = que.top();que.pop();
        int u = p.second;int d = p.first;
        if (d > dist[u])continue;
        for (re int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] > dist[u] + e.cost) {
                dist[e.to] = dist[u] + e.cost;
                fa[e.to] = u;
                que.push({ dist[e.to],e.to });
            }
            else if (dist[e.to] == dist[u] + e.cost && fa[e.to] > u)
                fa[e.to] = u;
        }
    }
}

bool used[max_n];
ll sum[max_n];
inline int dfs(int u) {
    if (used[u])return sum[u];
    used[u] = true;
    sum[u] = cs[u];
    for (re int i = head2[u];i;i = EE[i].next)
        sum[u] += dfs(EE[i].to);
    return sum[u];
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m >> t;
    for (re int i = 1;i <= n;++i)cin >> cs[i];
    for (re int i = 1;i <= m;++i) {
        int u, v, c;
        cin >> u >> v >> c;
        add(u, v, c);
        add(v, u, c);
    }dijstra(1);

    for (re int i = 2;i <= n;++i)
        add2(fa[i], i);
    for (re int i = 1;i <= n;++i)
        if (!used[i])dfs(i);
    ll ans = 0;
    for (re int i = 1;i <= n;++i)
        ans = max(ans, (dist[i] - t) * sum[i]);
    cout << ans << endl;
}