#include <bits/stdc++.h>
using namespace std;
long long n, m, t, A[100000], a, b, c, g1[100000], g2[100000], ans;
vector<pair<long long, long long>> v1[100000], v2[100000];
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
               greater<pair<long long, long long>>>
    q;
int main() {
  cin >> n >> m >> t;
  for (int i = 0; i < n; ++i) {
    cin >> A[i];
    g1[i] = g2[i] = 9223372036854775807;
  }
  for (int i = 0; i < m; ++i) {
    cin >> a >> b >> c;
    v1[a - 1].push_back(make_pair(b - 1, c));
    v2[b - 1].push_back(make_pair(a - 1, c));
  }
  g1[0] = 0;
  g2[0] = 0;
  for (int i = 0; i < v1[0].size(); ++i)
    q.push(make_pair(v1[0][i].second, v1[0][i].first));
  while (!q.empty()) {
    if (g1[q.top().second] == 9223372036854775807) {
      g1[q.top().second] = q.top().first;
      for (int i = 0; i < (int)v1[q.top().second].size(); ++i) {
        if (g1[v1[q.top().second][i].second] == 9223372036854775807)
          q.push(make_pair(v1[q.top().second][i].second + g1[q.top().second],
                           v1[q.top().second][i].first));
      }
    }
    q.pop();
  }
  for (int i = 0; i < v2[0].size(); ++i)
    q.push(make_pair(v2[0][i].second, v2[0][i].first));
  while (!q.empty()) {
    if (g2[q.top().second] == 9223372036854775807) {
      g2[q.top().second] = q.top().first;
      for (int i = 0; i < (int)v2[q.top().second].size(); ++i) {
        if (g2[v2[q.top().second][i].second] == 9223372036854775807)
          q.push(make_pair(v2[q.top().second][i].second + g2[q.top().second],
                           v2[q.top().second][i].first));
      }
    }
    q.pop();
  }
  ans = 0;
  for (int i = 0; i < n; ++i) {
    cout << i << ' ' << g1[i] << ' ' << g2[i] << endl;
    if (g1[i] != 9223372036854775807 && g2[i] != 9223372036854775807)
      ans = max(ans, (t - g1[i] - g2[i]) * A[i]);
  }
  cout << ans << endl;
  return 0;
}
