#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define int int64_t

#define rng(i, a, b) for (int i = a; i < b; i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = b - 1; i >= a; i--)
#define per(i, b) gnr(i, 0, b)

#define all(x) begin(x), end(x)
#define sz(x) int(size(x))

#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define f first
#define s second

using namespace std;
using namespace __gnu_pbds;

const int INF = 1e18;

void solve() {
    int n, m, t;
    cin >> n >> m >> t;

    vector<int> c(n);
    rep(i, n) {
        cin >> c[i];
    }

    vector<vector<pair<int, int>>> g(n);
    rep(i, m) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    vector<int> dist(n, INF);
    dist[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        int u = pq.top().s;
        pq.pop();
        for (auto [v, w] : g[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    vector<vector<int>> dg(n);
    rng(u, 1, n) {
        int to = INF;
        for (auto [v, w] : g[u]) {
            if (w + dist[v] == dist[u]) {
                to = min(to, v);
            }
        }
        dg[to].pb(u);
    }

    vector<int> dep(n);
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : dg[u]) {
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }

    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&](int a, int b) {
        return dep[a] > dep[b];
    });

    for (int u : ord) {
        for (int v : dg[u]) {
            c[u] += c[v];
        }
    }

    int ans = 0;
    rng(i, 1, n) {
        ans = max(ans, (dist[i] - t) * c[i]);
    }
    cout << ans << '\n';
}

int32_t main() {
#ifndef LOCAL
    freopen("shortcut.in", "r", stdin);
    freopen("shortcut.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }

    return 0;
}